POJ3321 苹果树

体会一下 树状数组是怎么用的，还是太菜了

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 3e5+10;
int L[maxn],R[maxn],timing;
int c[maxn],a[maxn];

int tot,head[maxn];
struct Edge{ int to,nxt;}e[maxn];
void add(int from,int to)
{
	e[tot].nxt = head[from]; e[tot].to = to;
	head[from] = tot++;
}
void dfs(int s)
{
	L[s] = ++timing;
	for(int i = head[s]; ~i; i = e[i].nxt)dfs(e[i].to); 
	R[s] = ++timing;
}
void update(int x,int ch)
{
	for(;x<=timing; x+=-x&x) c[x] += ch;
}
int sum(int x)
{
	int s = 0;
	for(;x > 0; x-=-x&x) s+=c[x];
	return s;
}
int main()
{
	memset(head,-1,sizeof(head)); tot = 0;
	int n; scanf("%d",&n);
	for(int i = 1,a,b; i < n; ++i)
	{
		scanf("%d%d",&a,&b);
		add(a,b); 
	}
	dfs(1);
	for(int i = 1; i <= timing; ++i) a[i] = 1,update(i,1);
	int k,pos; scanf("%d",&k);
	char op[2];
	while(k--)
	{
		scanf("%s",op);
		if(op[0]=='Q')
		{
			scanf("%d",&pos);
			printf("%d\n",(sum(R[pos])-sum(L[pos]-1))/2); 
		}
		else
		{
			scanf("%d",&pos);
			a[pos] = -a[pos];
			update(L[pos],a[pos]); update(R[pos],a[pos]);
		}
	}
}