poj 3321 Apple Tree（树状数组）

辉煌北大的月赛题质量真高啊，这种树状数组真难想到。

树状数组的基本用法是区间，单点的应用，起初这个怎么都想不到如何套用到树状数组。

转化方法是 将树上的节点信息查询，转为深度优先中节点顺序（代表结点编号）。进结点与出结点分别代表该结点管辖范围。

题目大意级是说，给你一颗树，最初每个节点上都有一个苹果，有两种操作：修改（即修改某一个节点，修改时这一个节点苹果从有到无，或从无到有）和查询（查询某一个节点他的子树上有多少个苹果）。

由于此题数据比较大(N<=10^5)，而且不是标准的二叉树，所以这里我们队每一个节点重新编号，另外为每一个节点赋一个左值和一个右值，表示这个节点的管辖范围。

也就是DFS搜索的时候做标记的过程，这样新的编号为1~6的节点所管辖的范围分别就是[1,6]  [2,4]   [3,3]  [4,4]  [5,6]  [6,6]，其中左边的是左值，右边的是右值，节点1的区间是[1,6]，正好这棵子树有6个节点，其他也一样

#include<cstdio>
#include<string> 
#include<string.h>
#include<iostream>
#include<algorithm> 
#include<map>
#include<iterator>
using namespace std;
#define N 100010
int n,m;


int lowbit(int x){return -x&x;}
void update(int *arr,int r,int num)
{
	int i;
	for(i=r;i<=n;i+=lowbit(i))
		arr[i]+=num;

}
int getsum(int *arr,int r)
{
	int i;
	int ans=0;
	for(i=r;i>0;i-=lowbit(i))
		ans+=arr[i];
	return ans;
}

int head[N];
int next[N];
int netb[N];
int deh1[N];
int deh2[N];
int cnt,depth;
int arr[N];
int a[N];
void init()
{
	int i;
	//memset(a,0,sizeof(a));
	memset(deh1,0,sizeof(deh1));
	memset(head,-1,sizeof(head));
	cnt=0;depth=0;
	for(i=1;i<=n;i++)
		update(arr,i,1),a[i]=1;

}
void add(int u,int v)
{
	netb[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
}
void dfs(int u)
{
	deh1[u]=++depth;//代表左
	int i;
	for(i=head[u];~i;i=next[i])
	{
		int v=netb[i];
			dfs(v);
	}
	deh2[u]=depth;//代表右
}
int main()
{
	int i,j,k,u,v,m;
	char str[10];
	while(~scanf("%d",&n))
	{
		init();
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&u,&v);
			add(u,v);//add(v,u);
		}
		dfs(1);
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			scanf("%s%d",str,&k);
			if(str[0]=='C') a[k]*=-1,update(arr,deh1[k],a[k]);//这里用deh1[k]左边也代表它的标号
			else 
			{
				u=deh1[k]-1;
				v=deh2[k];
				k=getsum(arr,v)-getsum(arr,u);
				printf("%d\n",k);
			}
		}
	}
	return 0;
}