14113: 【原4113】Seven Apples 0n a Witch’s Tree

题目

题目描述

author: 黄俊翔原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4113 ## Description

历经无数周折后，赫萝与罗伦斯最终在纽希拉安定下来，并开了一家温泉旅馆。为了让年幼的女儿缪莉时刻有苹果吃，赫萝在旅馆旁种了一棵苹果树。

这棵树具有魔法，因此它满足以下这样一些性质：它真的长成一棵树（数据结构意义上）的形状，并在每个节点上都长了且最多只长一个苹果，包括编号为1的根节点也是。赫萝时不时会从树上摘下一个苹果，而这颗树也时不时会从空的节点上长出一个苹果。

为了统计苹果的长势（翻译：嘴馋），缪莉有时会想要知道某一颗子树上总共有多少苹果。但这棵树有些巨大，年幼的缪莉有点数不过来，你能帮帮她吗？

Input Format

第一行包含一个正整数\(N\)，为苹果树的节点数。

接下来的\(N-1\)行，每行有两个正整数\(u,v\)，代表编号为\(v\)的节点的父亲是\(u\)节点。

接下来的一行包含一个正整数\(M\)，为接下来发生的事件数。

接下来\(M\)行，每行的内容可能是以下两种情况之一：

“\(C\ x\)”代表编号为\(x\)的节点上的苹果数量发生了变化。由于每个节点上最多只会长一个苹果，因此如果原来这个节点上有苹果，那这条信息就代表赫萝摘掉了这个苹果；如果原来这个节点上没有苹果，那这条信息就代表这个节点上长出了一个苹果。

“\(Q\ x\)”代表缪莉想要知道以节点\(x\)为根的子树上总共有多少个苹果。

Output Format

对于每个缪莉的询问输出一行，每行一个数字\(x\)代表问题的答案。

Sample Input

Sample Output

4
3

Data Range

对于\(30\%\)的数据，\(N,M \le 1000\)，。

对于另外\(30\%\)的数据，这颗苹果树是一颗完全二叉树。（满二叉树是完全二叉树的一种，区别在于完全二叉树是指仅最后一排可能非满，且最后一排的所有节点都靠到了最左；而满二叉树的最后一排也必然是满的）

对于\(100\%\)的数据，\(N,M \le 100000\)。

FineArtz's solution

/* Seven Apples 0n a Witch's Tree */
#include <iostream>
using namespace std;

const int MAXN = 100000;

int head[MAXN + 5], nxt[MAXN + 5], e[MAXN + 5], cnt = 0;
bool b[MAXN + 5] = {false};
int n, m, root = 0;
int in[MAXN + 5], out[MAXN + 5], seq[MAXN + 5], t = 0;
bool apple[MAXN + 5] = {false};

struct Node{
    int l = 0, r = 0, sum = 0;
};

Node a[MAXN * 4 + 5];

void addEdge(int u, int v){
    ++cnt;
    nxt[cnt] = head[u];
    e[cnt] = v;
    head[u] = cnt;
}

void dfs(int x){
    in[x] = t;
    seq[t] = x;
    for (int i = head[x]; i != 0; i = nxt[i]){
        ++t;
        dfs(e[i]);
    }
    out[x] = t;
}

void buildTree(int x, int l, int r){
    a[x].l = l;
    a[x].r = r;
    if (l == r){
        a[x].sum = 1;
        return;
    }
    int mid = (l + r) / 2;
    buildTree(x * 2, l, mid);
    buildTree(x * 2 + 1, mid + 1, r);
    a[x].sum = a[x * 2].sum + a[x * 2 + 1].sum;
};

void update(int x, int p, int d){
    if (a[x].l == a[x].r){
        a[x].sum += d;
        return;
    }
    int mid = (a[x].l + a[x].r) / 2;
    if (p <= mid)
        update(x * 2, p, d);
    else
        update(x * 2 + 1, p, d);
    a[x].sum = a[x * 2].sum + a[x * 2 + 1].sum;
}

int query(int x, int l, int r){
    if (a[x].l >= l && a[x].r <= r)
        return a[x].sum;
    int mid = (a[x].l + a[x].r) / 2;
    int ret = 0;
    if (mid >= l)
        ret += query(x * 2, l, r);
    if (mid < r)
        ret += query(x * 2 + 1, l, r);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        b[v] = true;
    }
    for (int i = 1; i <= n; ++i){
        if (!b[i]){
            root = i;
            break;
        }
    }
    t = 1;
    dfs(root);
    for (int i = 1; i <= n; ++i)
        apple[i] = true;
    buildTree(1, 1, n);

    cin >> m;
    while (m--){
        char op;
        int x;
        cin >> op >> x;
        if (op == 'C'){
            if (apple[x]){
                apple[x] = false;
                update(1, in[x], -1);
            }
            else{
                apple[x] = true;
                update(1, in[x], 1);
            }
        }
        else if (op == 'Q'){
            cout << query(1, in[x], out[x]) << '\n';
        }
    }
    return 0;
}