学步园

这个题很有趣，有一点数据结构和图论综合的感觉。

题目大意为：给出一个树（非二叉树），节点数从1编号至n。初始时每个节点都有一个苹果。现在有两种操作：

1.Q x，询问以x为根节点的子树的苹果个数的总合；

2.C x，改变x节点的值，若原来为1，则改为0；若原来为0，则改为1。

首先如何得到某个节点的子树的所有节点？可以前序遍历这课树，这样所有的儿子在遍历时的顺序一定是连续的。

在进入儿子们，先记录此时的序号，即根节点的序号；遍历完儿子们之后，再记录此时的序号，就得到了儿子们遍历顺序的起始和终结。

再把每个节点映射到他们被遍历的顺序，维护一个BIT即可。

还有一个纠结的地方就是存图。原先是直接用vector，t了，于是换了手写的edge结构体。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 100010
#define lowbit(x) (x & -x)

template <class T>
inline int RD(T &x)
{
        x = 0;
        char ch = getchar();
        while(!isdigit(ch)) { ch = getchar(); if(ch == EOF) return 0; }
        while(isdigit(ch)) { x *= 10; x += ch - '0'; ch = getchar(); }
        return 1;
}

int son[MAXN][2], a[MAXN], pre[MAXN];
int n, m, u, v, k, x, tot;
char op[4];

struct Edge
{
    int v, pre;
    Edge() {}
    Edge(int _v, int _pre): v(_v), pre(_pre) {}
}ee[MAXN];

void add_edge(int u, int v)
{
    ee[tot] = Edge(v, pre[u]);
    pre[u] = tot++;
}

void dfs(int rt)
{
    son[rt][0] = k++;
    for(int i = pre[rt]; i; i = ee[i].pre) dfs(ee[i].v);
    son[rt][1] = k - 1;
}

int sum(int i)
{
    int ret = 0;
    while(i > 0) ret += a[i], i -= lowbit(i);
    return ret;
}

void add(int i, int v)
{
    while(i <= n) a[i] += v, i += lowbit(i);
}

int main()
{
//    freopen("E.in", "r", stdin);

    RD(n);
    for(int i = 1; i <= n; i++) add(i, 1);
    tot = 1;
    memset(pre, 0, sizeof(pre));
    for(int i = 1; i <  n; i++)
    {
        RD(u), RD(v);
        add_edge(u, v);
    }
    k = 1; dfs(1);

    RD(m);
    while(m--)
    {
        op[0] = getchar(); RD(x);
        if(op[0] == 'Q') printf("%d\n", sum(son[x][1]) - sum(son[x][0] - 1));
        if(op[0] == 'C')
        {
            int tmp = sum(son[x][0]) - sum(son[x][0] - 1);
            tmp = tmp > 0 ? -1 : 1;
            add(son[x][0], tmp);
        }
    }
    return 0;
}