poj-3321 Apple Tree
來源：程序員人生 發布時間：2015-08-13 08:10:13 閱讀次數：2528次
題意：
給定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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
