poj-3321 Apple Tree
来源：程序员人生 发布时间：2015-08-13 08:10:13 阅读次数：2273次
题意：
给定1棵有根树，开始时每一个节点有苹果；
有两种操作 C
x :使x节点的状态改变，有果子变成没有，没有就变成有；
Q x
:查询x节点子树上的果子总数；
n,m<=1^5
题解：
范围明显不能爆搜，所以我们在求和的时候不能枚举；
可以想到用树状数组来保护和；
所以基本想法就是使子树们各自在1个区间上，然后树状数组保护；
制作这个区间就用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
",&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],⑴);
else
a[x]=1,update(data[x], 1);
}
else
{
scanf("%d",&x);
printf("%d
",query(en[x])-query(data[x]⑴));
}
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
