题意：一棵树，有很多分叉，每个分叉上最多有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=100010; int n,m,val=0,tot=0; //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=0; while(i) { sum+=c[i]; i-=lowbit(i); } return sum; } //dfs后根遍历，求取每个节点在树状数组中的顺序编号，以及每棵子树的left_leaf值 void dfs(int u) { if(head[u]==-1) { hash_value[u]=++val; left_leaf[u]=u; return; } int v,flag=1; for(int k=head[u]; k!=-1; k=edge[k].next) { v=edge[k].to; dfs(v); if(flag) { //这里的v即使父节点u的最先访问的子节点 left_leaf[u]=left_leaf[v]; flag=0; } } hash_value[u]=++val; } int main() { int u,v; memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1; i<n; i++) { scanf("%d%d",&u,&v); add(u,v); } dfs(1); memset(c,0,sizeof(c)); for(int i=1; i<=n; i++) { a[i]=1; update(i,1); } scanf("%d",&m); char str[5]; int l,r; for(int i=0; i<m; i++) { scanf("%s%d",str,&u); if(str[0]=='Q') { r=hash_value[u]; l=left_leaf[u]; l=hash_value[l]; //[l,r]即为以u为根节点的子树在树状数组中的区间 printf("%d ",sum(r)-sum(l-1)); } else { r=hash_value[u]; if(a[r]==1) { a[r]=0; update(r,-1); } else { a[r]=1; update(r,1); } } } return 0; }
也可以用结构体，来存储每个以节点i为根节点的子树在树状数组中的区间左端点和右端点：
代码二：
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn=100005; int n,m; int c[maxn]; //树状数组 bool a[maxn]; //用来标记该节点是否有苹果 int cnt=1; int head[maxn]; int tot=0; 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]==-1) { apple[u].l=apple[u].r=cnt; cnt++; return; } apple[u].l=cnt; for(int k=head[u]; k!=-1; 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=0; while(i) { res+=c[i]; i-=lowbit(i); } return res; } int main() { char str[3]; int u,v; memset(head,-1,sizeof(head)); memset(a,true,sizeof(a)); scanf("%d",&n); for(int i=0; i<n-1; i++) { scanf("%d%d",&u,&v); add(u,v); } dfs(1); scanf("%d",&m); //初始时，每个节点数都有一个苹果 for(int i=1; i<=n; i++) update(apple[i].r,1); for(int i=1; i<=m; i++) { scanf("%s%d",str,&u); if(str[0]=='C') { if(a[u]) { update(apple[u].r,-1); a[u]=false; } else { update(apple[u].r,1); a[u]=true; } } else { printf("%d ",sum(apple[u].r)-sum(apple[u].l-1)); } } return 0; }