第一次做树状数组，这个东西还是蛮神奇的，通过一个简单的C数组就可以表示出整个序列的值，并且可以用logN的复杂度进行改值与求和。
这道题目我根本不知道怎么和树状数组扯上的关系，刚开始我想直接按图来遍历来做，后来用树状数组做完都跑了600+MS，那样估计是TLE了。
做法就是用DFS把整个图重建一遍，代号小的点在叶子，代号大的点为根。记录每个根的起始点号为 idl，根点号为 idh，则求某个根的苹果和就直接调用树状数组的sum即可。
不过前提是要建好树，我一开始不明白为什么要建一颗标准树，即就是按1 2 3 4。。。。，每个点有一个苹果的递增的标准树，因为整个图并不是按这个标准来建得，2号点C值为1号和2号的和，但实际的树可能1号和2号都是叶子啊。。。。后来想清楚了，每次求和都是建立在某个根上，而这个根和它的所有孩子是符合标准树状数组的。
#include <cstdio> #include <cstring> #define N 100010 using namespace std; int u[N],v[N],nt[N],ft[N],idh[N],idl[N],cnt,isapple[N],c[N]; void add(int a,int b) { u[cnt]=a; v[cnt]=b; nt[cnt]=ft[a]; ft[a]=cnt++; } int n; void dfs(int x) { idl[x]=cnt; if (ft[x]==-1) { idh[x]=cnt++; return; } for (int i=ft[x];i>=0;i=nt[i]) { int nx=v[i]; dfs(nx); } idh[x]=cnt++; } int lowbit(int x) { return x & (-x); } void update(int x) { int d; if (isapple[x]) { d=-1; isapple[x]^=1; } else { d=1; isapple[x]^=1; } while (x<=n) { c[x]+=d; x+=lowbit(x); } } int getsum(int x) { int ret=0; while (x>0) { ret+=c[x]; x-=lowbit(x); } return ret; } int main() { int m; while (scanf("%d",&n)!=EOF) { cnt=0; int a,b; memset(ft,-1,sizeof ft); memset(c,0,sizeof c); for (int i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); } cnt=1; dfs(1); for (int i=1;i<=n;i++) { isapple[i]=0; update(i); } //puts("pp"); scanf("%d",&m); char ch[2]; int nt; while (m--) { // puts("pass"); scanf("%s%d",ch,&nt); //puts(ch); if (ch[0]==‘Q‘) { int ans=getsum(idh[nt])-getsum(idl[nt]-1);//求结果的时候就求根的sum以及最小叶子的前一点，相减就是该棵树的和，就跟前缀和一样的原理 printf("%d\n",ans); } else { update(idh[nt]); } //getchar(); } } return 0; }