給出一棵樹，判斷 以 某個 節點 為 根 的子樹 有多少個節點有蘋果。。
知道要用樹狀數組求和，但是 每個子樹節點編號不連續，頭疼，後來看了一些大神的報告才 恍然大悟。
可以先進行一次 dfs 後序遍歷，對 每個節點重新編號，使子樹的每個節點編號連續，並且根節點編號最大，同時要記錄每棵子樹的范圍
即 子樹 的最大編號和最小編號，然後 樹狀數組。。
ps：建樹也不太會。。
[cpp]
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100005
struct Edge{
int v,next;//v記錄邊頭部，next記錄下一邊
}edge[MAXN];
struct Range{//存每個子樹范圍
int low,high;
}range[MAXN];
int root[MAXN];// root[u]以u為根的節點編號
int c[MAXN];
int app[MAXN];//the state of point
int index,n,m;
inline void addEdge(int u,int v){//加邊，將節點插入頭部
edge[index].v=v;
edge[index].next=root[u];
root[u]=index++;
}
inline void dfs(int u){//後序遍歷
range[u].low=index;//記錄最小編號
if(root[u]==-1){
range[u].high=index++;
return;
}
else {
for(int i=root[u];i!=-1;i=edge[i].next){
dfs(edge[i].v);
}
}
range[u].high=index++;//記錄最大編號，即根的編號
}
inline int lowbit(int x){
return x&(-x);
}
inline void update(int i,int v){
while(i<=n){
c[i]+=v;
i+=lowbit(i);
}
}
inline int getsum(int i){
int sum=0;
while(i>0){
sum+=c[i];
i-=lowbit(i);
}
return sum;
}
int main(){
int i,j;
int u,v;
char cmd;
while(scanf("%d",&n)==1){
memset(root,-1,sizeof(root));
index=1;
for(i=1;i<n;i++){
scanf("%d%d",&u,&v);
addEdge(u,v);
}
fill(app,app+n+5,1);
for(i=1;i<=n;i++)c[i]=lowbit(i);//初始化，一開始每個節點都有 apple
index=1;
dfs(1);
scanf("%d",&m);
while(m--){
scanf(" %c%d",&cmd,&u);
if(cmd=='C'){
int val=1;
if(app[u])val=-1;
app[u]=!app[u];
update(range[u].high,val);
}
else {
int val=getsum(range[u].high)-getsum(range[u].low-1);
printf("%d\n",val);
}
}
}
return 0;
}
/*
10
1 5 3
3 2
1 3
5 7
10 9
10 8
5 10
5 6
100
Q 1
10
Q 2
1
C 10
Q 1
9
Q 10
2
C 10
Q 10
3
*/
作者：qingniaofy
