题目大意：一棵树（不一定是二叉树！！），树的节点上本来都有一个苹果，要求完成以下操作：
1.指定某个节点，如果这个节点原本有苹果则拿去，如果没有苹果则填上一个苹果
2.询问某个节点以及其子树一共有多少个苹果
思路：dfs这棵树，记录下第一次到达这个节点的时间以及遍历离开的时间，于是一个节点就成了一个区间，左端点和右端点分别是开始遍历的时间和结束遍历的时间，区间里夹着的就是这个节点的子树！！区间端点记录有没有苹果，这样问题就变成了询问一个区间和的问题，而加减苹果就是对区间端点+1和-1 这两个操作都能用树状数组解决
#include<cstdio>
#include<string.h>
#include<iostream>
#define maxn 200009
using namespace std;
intnow=0,tree[maxn]={0},n,next[maxn]={0},root[maxn]={0},edge[maxn]={0},start[maxn]={0},end[maxn]={0};
int lowbit(int x){return x &(-x);}
void add(int x,int c)
{
while (x<=2*n)
{
tree[x]+=c;
x+=lowbit(x);
}
}
int get(int x)
{
int sum=0;
for(int i=x;i>=1;i=i-lowbit(i))sum+=tree[i];
return sum;
}
void addedge(int x,int y)
{
next[++now]=root[x];
edge[now]=y;
root[x]=now;
}
void dfs(int j)
{
start[j]=++now;
for(int i=root[j];i!=0;i=next[i])dfs(edge[i]);
end[j]=++now;
}
int main()
{
int x,y,m,ope,flag;
char ch[2];
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
}
now=0;
dfs(1);
for(int i=1;i<=2*n;i++)
add(i,1);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s%d",ch,&ope);
if (ch[0]=='Q')
{
printf("%d ",(get(end[ope])-get(start[ope]-1))>>1);
}
else
{
flag=get(end[ope])-get(end[ope]-1);
if (flag==1)flag=-1;else flag=1;
add(start[ope],flag);
add(end[ope],flag);
}
}
return 0;
}
调试结果：1次AC