題意：有一棵樹，樹上有一些叉，每個叉上剛開始都有一個蘋果，對每個叉可以有兩種操作，若剛開始有蘋果，則變為沒蘋果，若剛開始沒蘋果，則變為有一個蘋果。有多次操作，有多次詢問，對於每次詢問，回答該結點以及該結點以上有多少個蘋果。
思路：樹狀數組的好題。首先可以dfs樹，為每個結點映射一個區間，然後就是樹狀數組的裸題了。樹狀數組不僅可以應用在普通題目上，而且可以自己構造區間。
代碼：
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 100010;
int up[N],down[N],head[N],order,n,numedge,num[N],dit[N];
struct edge{
int lp,rp,next;
}ee[N * 2];
void init(){
order = 1;
numedge = 0;
memset(up,0,sizeof(up));
memset(down,0,sizeof(down));
memset(head,-1,sizeof(head));
for(int i = 1; i <= N - 10; ++i)
num[i] = ( i & (-i) );
}
void add_edge(int x,int y){
ee[numedge].lp = x;
ee[numedge].rp = y;
ee[numedge].next = head[x];
head[x] = numedge++;
}
void dfs(int x){
down[x] = order;
for(int i = head[x]; i != -1; i = ee[i].next){
int y = ee[i].rp;
dfs(y);
}
up[x] = order++;
}
int lowbit(int x){
return x & (-x);
}
int sum(int x){
int s = 0;
while(x > 0){
s += num[x];
x -= lowbit(x);
}
return s;
}
void update(int x,int add){
while(x < N){
num[x] += add;
x += lowbit(x);
}
}
int main(){
scanf("%d",&n);
init();
int x,y;
for(int i = 1; i < n; ++i){
scanf("%d%d",&x,&y);
dit[x] = dit[y] = 1;
add_edge(x,y);
}
dfs(1);
int m;
scanf("%d",&m);
char ss[3];
while(m--){
scanf("%s%d",ss,&x);
if(ss[0] == 'Q'){
printf("%d\n",sum(up[x]) - sum(down[x] - 1));
}
else{
if(dit[x])
update(up[x],-1);
else
update(up[x],1);
dit[x] = !dit[x];
}
}
return 0;
}
