题意:
树杈上长苹果,统计苹果数.
思路:
将树通过dfs映射到线性序列, 用树状数组计数.
#include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 100010; int n,m; int head[MAXN],num; struct pool { int v,next; }g[MAXN]; void add(int u, int v) { g[++num].v = v; g[num].next = head[u]; head[u] = num; } inline int lowbit(int x) { return x&(-x); } int l[MAXN],r[MAXN]; void dfs(int u) { l[u] = ++num; for(int i=head[u];i;i=g[i].next) { //printf("i = %d, dfs(%d);\n",i,g[i].v); dfs(g[i].v); } r[u] = num; } int a[MAXN],c[MAXN]; int sum(int x) { int ans = 0; for(;x>0;x^=lowbit(x)) ans += c[x]; return ans; } void modify(int x, int d) { for(;x<=n;x+=lowbit(x)) c[x] += d; } int main() { scanf("%d",&n); for(int i=0,v,u;i<n-1;i++) { scanf("%d%d",&u,&v); add(u, v); } num = 0; // printf("&&&"); dfs(1); // printf("***"); for(int i=1;i<=n;i++)//init { a[i] = 1; c[i] = lowbit(i); } scanf("%d",&m); char s[5]; while(m--) { scanf("%s%d",s,&num); if(s[0]=='C') { modify(l[num],a[num]?-1:1); a[num] ^= 1; } else printf("%d\n",sum(r[num])-sum(l[num]-1)); } }