题目链接：http://poj.org/problem?id=3321
给你n个点，n-1条边，1为根节点。给你m条操作，C操作是将x点变反(1变0，0变1)，Q操作是询问x节点以及它子树的值之和。初始所有的节点为1。
用DFS序的方法将以1为根节点DFS遍历所有的节点，L[i]表示i点出现的最早的时间戳，R[i]表示i点出现的最晚的时间戳，每个节点出现两次。
所以要是查询 i 及它子树的值的和之话，只要用树状数组查询L[i]~R[i]之间的值然后除以2，复杂度log(n)。改变操作的话，只要改变下标为L[i]以及R[i]上的值就可以了。
类似的题目有HDU3974，不过是线段树成段更新，也是用DFS序的方法写的。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 2e5 + ;
const int INF = 1e9;
int head[MAXN] , n , m , cnt , L[MAXN] , R[MAXN] , bit[MAXN * ] , dfn , a[MAXN];
//a数组表示每个元素的值
struct data {
int next , to;
}edge[MAXN * ]; inline void add_edge(int u , int v) {
edge[cnt].next = head[u];
edge[cnt].to = v;
head[u] = cnt++;
} void dfs(int u , int par) {
L[u] = ++dfn;
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == par)
continue;
dfs(v , u);
}
R[u] = ++dfn;
} inline void add(int i , int x) {
for( ; i <= dfn ; i += (i & -i))
bit[i] += x;
} int sum(int i) {
int s = ;
for( ; i >= ; i -= (i & -i))
s += bit[i];
return s;
} int main()
{
int u , v;
char q[];
while(~scanf("%d" , &n)) {
memset(head , - , sizeof(head));
memset(bit , , sizeof(bit));
memset(a , , sizeof(a));
cnt = dfn = ;
for(int i = ; i < n ; i++) {
scanf("%d %d" , &u , &v);
add_edge(u , v);
add_edge(v , u);
}
dfs( , -);
scanf("%d" , &m);
while(m--) {
scanf("%s %d" , q , &u);
if(q[] == 'Q') {
printf("%d\n" , ((R[u] - L[u] + ) - (sum(R[u]) - sum(L[u] - ))) / ); //除2因为dfs序中 每个点出现2次
}
else {
if(a[u]) {
add(L[u] , -);
add(R[u] , -);
a[u] = ;
}
else {
add(L[u] , );
add(R[u] , );
a[u] = ;
}
}
}
}
}