POJ3321Apple Tree Dfs序树状数组

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

出自——博客园-zhouzhendong

~去博客园看该题解~

题目

POJ3321 Apple Tree

题意概括

有一颗01树，以结点1为树根，一开始所有的结点权值都是1，有两种操作：

1.改变其中一个结点的权值（0变1，1变0）

2.询问子树X的节点权值和。

输入描述

一组数据。

先是一个数n，表示有n个节点。

接下去n-1行，每行表示一条边。

然后一个数m，表示有m个操作。

然后m行，每行一个字母一个数x，如果字母是Q，则是询问；否则是修改。

输出描述

每一个询问一行，表示答案。

题解

直接把题目变成dfs序上单点修改和区间sum询问的问题。

单点修改，不用线段树，树状数组就可以了。

如果你非要用线段树我也不拦你……

代码

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=+,M=N*;
struct Edge{
int cnt,y[M],nxt[M],fst[N];
void set(){
cnt=;
memset(fst,,sizeof fst);
}
void add(int a,int b){
y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;
}
}e;
int n,m;
int in[N],out[N],time;
int tree[N],v[N];//树状数组
int lowbit(int x){
return x&-x;
}
void dfs(int prev,int rt){
in[rt]=++time;
for (int i=e.fst[rt];i;i=e.nxt[i])
if (e.y[i]!=prev)
dfs(rt,e.y[i]);
out[rt]=time;
}
void update(int x,int d){
for (;x<=n;x+=lowbit(x))
tree[x]+=d;
}
int sum(int x){
int ans=;
for (;x>;x-=lowbit(x))
ans+=tree[x];
return ans;
}
int query(int L,int R){
return sum(R)-sum(L-);
}
int main(){
e.set();
scanf("%d",&n);
for (int i=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
e.add(a,b);
e.add(b,a);
}
time=;
dfs(,);
for (int i=;i<=n;i++)
tree[i]=lowbit(i),v[i]=;
scanf("%d",&m);
for (int i=,x;i<=m;i++){
char ch[];
scanf("%s%d",ch,&x);
if (ch[]=='Q')
printf("%d\n",query(in[x],out[x]));
else
update(in[x],-v[x]*),v[x]^=;
}
return ;
}