dfs序可以维护一个子树内的信息
需要记录dfs进的时间以及所有子树都遍历完的时间
void dfs(int u, int fa)
{L[u] = ++id;for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if(v == fa) continue;dfs(v, u);}R[u] = id;
}那么对于点i，L[i]到R[i]就是i的子树（包括i）
那么子树内维护信息就可以用树状数组，线段树之内的乱搞了。
poj 3321
用树状数组维护就好。
注意修改的时候一定是修改序列
#include<cstdio>
#include<cstring>
#include<cctype>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
struct Edge{ int to, next; };
Edge e[MAXN << 1];
int head[MAXN], num, n, m;
int L[MAXN], R[MAXN], s[MAXN], id;struct Binary_Index_Tree
{int f[MAXN];Binary_Index_Tree() { memset(f, 0, sizeof(f)); }int lowbit(int x) { return x & (-x); }void add(int x, int p){while(x <= n){f[x] += p; x += lowbit(x);}}int sum(int x){int res = 0;while(x){res += f[x];x -= lowbit(x);}return res;}int query(int l, int r) { return sum(r) - sum(l - 1); }
}S;void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}void AddEdge(int to, int from)
{e[num] = Edge{to, head[from]};head[from] = num++;
}void dfs(int u, int fa)
{L[u] = ++id;for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if(v == fa) continue;dfs(v, u);}R[u] = id;
}int main()
{memset(head, -1, sizeof(head)); num = 0;read(n);REP(i, 1, n){int u, v; read(u), read(v);AddEdge(u, v); AddEdge(v, u); }_for(i, 1, n) {s[i] = 1;S.add(i, 1);}dfs(1, -1);read(m);while(m--){char op[5]; int x;scanf("%s", op); read(x);if(op[0] == 'Q') printf("%d\n", S.query(L[x], R[x]));else{int id = L[x];if(s[id]) S.add(id, -1);else S.add(id, 1);s[id] = !s[id];}}return 0;
}