当初听郭炜老师讲时不是很懂，几个月内每次复习树状数组必看的题
树的dfs序映射在树状数组上进行单点修改，区间查询。
/*
树状数组：
lowbit[i] = i&-i
C[i] = a[i-lowbit[i]+1]+...+a[i] 求和：
设sum[k] = a[1]+a[2]+...+a[k]
则a[i]+a[i+1]+...+a[j] = sum[j]-sum[i-1]
在树状数组上：sum[k] = C[n1]+C[n2]+...+C[k]
n1 = n2-lowbit[n2]... >0 更新:
如果a[i]更新了,则以下几项也要更新
C[n1], C[n2], ... C[nm]
n1 = i, n2 = n1+lowbit[n1].. nm<=N 建树：O(N)
C[k] = sum[k]-sum[k-lowbit[k]] poj3321
树状数组：单点更新
书上长满了苹果，每一个节点有长苹果和不长两种状态
操作1：改变树枝上有无苹果的状态
操作2：询问某一树枝节点以下的所有的苹果有多少 做一次dfs，几下每个节点的开始时间Start[i]和结束时间End[i]
对于i节点的所有子孙的开始时间和结束时间都应该位于Start[i]和End[i]之间
C[i]是树状数组节点对应的苹果数 然后用树状数组C统计Start[i]到End[i]之间的附加苹果总数
树状数组统计区间可以用Sum(End[i])-Sum(Start[i]-1)来计算
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define MAXN 220000
using namespace std;
int C[MAXN];
vector<vector<int> > G(MAXN/);//树
int Lowbit[MAXN];
int Start[MAXN];
int End[MAXN];
bool HasApple[MAXN/];
int nCount;
//dfs搜索出所有状态
void dfs(int v){
Start[v] = ++nCount;
for (int i = ; i != G[v].size(); i++)
dfs(G[v][i]);
End[v] = ++nCount;
}
//求1-p的和
int QuerySum(int p){
int nSum = ;
while(p > ){
nSum += C[p];
p -= Lowbit[p];
}
return nSum;
}
//修改节点p的值
void Modify(int p, int val){
while(p <= nCount){
C[p] += val;
p += Lowbit[p];
}
}
int main(){
int n;
scanf("%d", &n);
int x, y;
int i, j, k;
for (i = ; i < n-; i++){
int a, b;
scanf("%d%d", &a, &b);
G[a].push_back(b);
}
nCount = ;
dfs();//从根节点开始dfs //树状数组要处理的原石数组下标范围
for (i = ; i <= nCount; i++)
Lowbit[i] = i&(-i); for(i = ; i <= n; i++)
HasApple[i] = ; int m;
//建树求C数组，即树状数组的节点值
for(i = ; i <= nCount; i++)
C[i] = i-(i-Lowbit[i]);
//C[i] = Sum[i] - Sum[i-Lowbit[i]]; scanf("%d", &m);
for (int i = ; i < m; i++){
char cmd[];
int a;
scanf("%s%d", cmd, &a);
//改变某个节点上的苹果的状态
if (cmd[] == 'C') {
if(HasApple[a] == ){
Modify(Start[a], -);
Modify(End[a], -);
HasApple[a] = ;
}
else {
Modify(Start[a], );
Modify(End[a], );
HasApple[a] = ;
}
}
//查询某个节点上的苹果
else {
int t1 = QuerySum(Start[a]-);
int t2 = QuerySum(End[a]);
cout << (t2-t1)/ << endl;
}
}
}