poj-3321 Apple Tree

浏览数：17 / 时间：2015年06月11日

题意：

给定一棵有根树，开始时每个节点有苹果；

有两种操作 C x :使x节点的状态改变，有果子变成没有，没有就变成有；

Q x :查询x节点子树上的果子总数；

n,m<=1^5

题解：

范围显然不能爆搜，所以我们在求和的时候不能枚举；

可以想到用树状数组来维护和；

所以基本想法就是使子树们各自在一个区间上，然后树状数组维护；

制作这个区间就用dfs，回溯时正好记录了整棵子树的信息；

具体还是看代码吧，深搜的过程之类的；

卡vector

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 100001
using namespace std;
int next[N<<1],head[N],to[N<<1];
int tree[N],data[N],en[N],tot,cnt;
bool a[N];
char str[100];
void add(int x,int y)
{
	to[++cnt]=y;
	next[cnt]=head[x];
	head[x]=cnt;
}
int lowbit(int k)
{
	return k&(-k);
}
void update(int k,int val)
{
	while(k<=N)
	{
		tree[k]+=val;
		k+=lowbit(k);
	}
}
int query(int k)
{
	int ret=0;
	while(k)
	{
		ret+=tree[k];
		k-=lowbit(k);
	}
	return ret;
}
void dfs(int x,int pre)
{
	int i,y;
	update(x,1);
	a[x]=1;
	data[x]=++tot;
	for(i=head[x];i;i=next[i])
	{
		if((y=to[i])!=pre)
		{
			dfs(y,x);
		}
	}
	en[x]=tot;
}
int main()
{
	int n,m,i,j,k,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1,0);
	scanf("%d\n",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%s",str);
		if(str[0]=='C')
		{
			scanf("%d",&x);
			if(a[x])
				a[x]=0,update(data[x],-1);
			else
				a[x]=1,update(data[x], 1);
		}
		else
		{
			scanf("%d",&x);
			printf("%d\n",query(en[x])-query(data[x]-1));
		}
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

poj-3321 Apple Tree