POJ 3321 Apple Tree dfs序的应用

题目链接

dfs序 说来很简单，却从来没有想到过。必须得深刻反省一下到底自己学了些啥。

题目大意是给你一棵树，动态统计某个子树的节点权值和。

同上一道题，裸算法。

利用dfs把一个树应设在一个序列上，方法是对每一次进栈出栈加一个时间戳，在这之间的点都是它的子节点。

然后就变成了动态统计区间和的问题了，

据说线段树会超。。

但是这种简单的求和问题，树状数组绝对是不二之选，用不着去折腾线段树了。

#include <cstdio>
#include <cstdlib>
#define N 210100
struct NODE {
    int v,next;
} a[N],st[N];
int h[N],t[N],P1[N],P2[N];
int tt,n,m,stn;
void dfs(int v) {
P1[v]=++tt;
for ( int p = a[v].next; p; p=st[p].next ) dfs(st[p].v);
P2[v]=tt;
return;
}
inline int l(int i) {
return i & -i;
}
void update(int x,int k) {
while (x<=n) {
t[x] += k;
x += l(x);
}
}
int gs(int x) {
int s =0;
while ( x) {
s += t[x];
x -= l(x);
}
return s;
}
int main() {
scanf("%d",&n);
for ( int i(1); i<n; i++) {
int a1,a2;
scanf("%d%d",&a1,&a2);
st[++stn].v = a2;
st[stn].next = a[a1].next;
a[a1].next = stn;
}
dfs(1);
for ( int i(1); i<=n; i++) h[i]=1,update(P1[i],1);
for ( scanf("%d\n",&m); m–;) {
char ch;
int x;
scanf("%c%d\n",&ch,&x);
if ( ch == ‘C’ ) {
if ( h[x] ) update(P1[x],-1);
else update(P1[x],1);
h[x] = 1-h[x];
} else
printf("%d\n",gs(P2[x])-gs(P1[x]-1));
}
return 0;
}