题意：一棵树，有很多分叉，每个分叉上最多有1个苹果。
给出n，接下来n-1行，每行u,v，表示分叉u,v之间有树枝相连。这里数据中u相当于树中的父节点，v相当于子节点。
给出两个操作：
1.C x 如果分叉x有一个苹果，表示该苹果被摘下；如果没苹果，表示该分叉长出1个苹果。
2.Q x 查询以分叉x为根节点的子树中所含有的苹果，包括分叉x。
思路：用树的后根遍历将树转化成一个序列，然后用树状数组维护。
树的后根遍历(先遍历每棵子树，再遍历根节点)实质上是按照自下而上、从左至右的顺序将非线性结构的树转化为一个线性序列。
每棵子树对应这个线性序列的一个连续的子区间，这样就可以用树状数组来维护更新。
原本我用vector超时，改用邻接表AC 。
代码一：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector> using namespace std;
const int maxn=;
int n,m,val=,tot=; //val即为树状数组中的顺序编号，tot为邻接表的边序号
int c[maxn]; //树状数组
int a[maxn]; //a[i]表示分叉i的苹果的值，0或1
int hash_value[maxn]; //hash_value[i]表示分叉i在树状数组中的序号
int left_leaf[maxn]; //left_leaf[i]表示以i为根节点的子树中最左底端的叶子节点的编号，该值的hash_value即为以i为根节点的子树在树状数组中的区间的最左端
int head[maxn]; struct Edge {
int to,next;
} edge[maxn]; void add(int u,int v) {
edge[tot].next=head[u];
edge[tot].to=v;
head[u]=tot++;
}
int lowbit(int x) {
return x&(-x);
}
void update(int i,int val) {
while(i<=n) {
c[i]+=val;
i+=lowbit(i);
}
}
int sum(int i) {
int sum=;
while(i) {
sum+=c[i];
i-=lowbit(i);
}
return sum;
}
//dfs后根遍历，求取每个节点在树状数组中的顺序编号，以及每棵子树的left_leaf值
void dfs(int u) {
if(head[u]==-) {
hash_value[u]=++val;
left_leaf[u]=u;
return;
}
int v,flag=;
for(int k=head[u]; k!=-; k=edge[k].next) {
v=edge[k].to;
dfs(v);
if(flag) {
//这里的v即使父节点u的最先访问的子节点
left_leaf[u]=left_leaf[v];
flag=;
}
}
hash_value[u]=++val;
}
int main() {
int u,v;
memset(head,-,sizeof(head));
scanf("%d",&n);
for(int i=; i<n; i++) {
scanf("%d%d",&u,&v);
add(u,v);
}
dfs();
memset(c,,sizeof(c)); for(int i=; i<=n; i++) {
a[i]=;
update(i,);
} scanf("%d",&m);
char str[];
int l,r;
for(int i=; i<m; i++) {
scanf("%s%d",str,&u);
if(str[]=='Q') {
r=hash_value[u];
l=left_leaf[u];
l=hash_value[l];
//[l,r]即为以u为根节点的子树在树状数组中的区间
printf("%d\n",sum(r)-sum(l-));
} else {
r=hash_value[u];
if(a[r]==) {
a[r]=;
update(r,-);
} else {
a[r]=;
update(r,);
}
}
}
return ;
}
也可以用结构体，来存储每个以节点i为根节点的子树在树状数组中的区间左端点和右端点：
代码二：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std;
const int maxn=;
int n,m;
int c[maxn]; //树状数组
bool a[maxn]; //用来标记该节点是否有苹果
int cnt=;
int head[maxn];
int tot=; struct Edge {
int next,to;
} edge[maxn]; struct Apple {
int l,r; //apple[u]的l和r表示以u为根的子树在树状数组中对应区间
} apple[maxn]; void add(int u,int v) {
edge[tot].next=head[u];
edge[tot].to=v;
head[u]=tot++;
}
//dfs，从节点u出发，计算即节点u为根的子树区间[apple[u].l,apple[u].r]
void dfs(int u) {
if(head[u]==-) {
apple[u].l=apple[u].r=cnt;
cnt++;
return;
}
apple[u].l=cnt;
for(int k=head[u]; k!=-; k=edge[k].next) {
int v=edge[k].to;
dfs(v);
}
apple[u].r=cnt++;
}
int lowbit(int x) {
return x&(-x);
}
void update(int i,int v) {
while(i<=cnt) {
c[i]+=v;
i+=lowbit(i);
}
}
int sum(int i) {
int res=;
while(i) {
res+=c[i];
i-=lowbit(i);
}
return res;
}
int main() {
char str[];
int u,v;
memset(head,-,sizeof(head));
memset(a,true,sizeof(a));
scanf("%d",&n);
for(int i=; i<n-; i++) {
scanf("%d%d",&u,&v);
add(u,v);
}
dfs();
scanf("%d",&m);
//初始时，每个节点数都有一个苹果
for(int i=; i<=n; i++)
update(apple[i].r,);
for(int i=; i<=m; i++) {
scanf("%s%d",str,&u);
if(str[]=='C') {
if(a[u]) {
update(apple[u].r,-);
a[u]=false;
} else {
update(apple[u].r,);
a[u]=true;
}
} else {
printf("%d\n",sum(apple[u].r)-sum(apple[u].l-));
}
}
return ;
}