Poj3321 Apple Tree dfs序 + 树状数组

Poj3321 Apple Tree
dfs序 + 树状数组
单点加区间询问
 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <iostream> 
 7 #include <iomanip>
 8 using namespace std ; 
 9 
10 const int maxn = 100011 ; 
11 struct node{
12     int to,pre ; 
13 }e[maxn*2];
14 char s[2] ; 
15 int n,Q,TI,cnt,ans ; 
16 int head[maxn],IN[maxn],OUT[maxn],dfs_id[maxn],a[maxn],tree[maxn] ; 
17 
18 inline int read() 
19 {
20     int x = 0 , f = 1 ;
21     char ch = getchar() ; 
22     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 
23     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; }
24     return x * f ; 
25 }
26 
27 inline void add(int x,int y) 
28 {
29     e[++cnt].to = y ; 
30     e[cnt].pre = head[x] ; 
31     head[x] = cnt ; 
32 }
33 
34 inline void dfs(int u,int fa) 
35 {
36     int v ; 
37     IN[ u ] = ++TI ; 
38     dfs_id[ TI ] = u ; 
39     for(int i=head[u];i;i = e[ i ].pre) 
40     {
41         v = e[ i ].to ; 
42         if(v!=fa) 
43             dfs(v,u) ;  
44     }
45     OUT[ u ] = TI ; 
46 }
47 
48 inline int lowbit(int x) 
49 {
50     return x&(-x) ; 
51 }
52 
53 inline void updata(int pos)  
54 {
55     int val = ( a[pos]^1 ) - a[pos] ;  
56     a[pos]^=1 ; 
57     for(int i=pos;i<=TI;i+=lowbit(i)) 
58         tree[ i ]+=val ;  
59 }
60 
61 inline int query(int pos) 
62 {
63     int ans = 0 ; 
64     for(int i=pos;i;i-=lowbit(i)) 
65          ans+=tree[ i ] ; 
66     return ans ; 
67 }
68 
69 int main() 
70 {
71     n = read() ;  ; 
72     int x,y ; 
73     for(int i=1;i<n;i++) 
74     {
75         x = read() ;  y = read() ; 
76         add(x,y) ; add(y,x) ; 
77     }
78     dfs(1,-1) ; 
79     for(int i=1;i<=TI;i++) updata( i ) ; 
80     Q = read() ;
81     for(int i=1;i<=Q;i++) 
82     {
83         scanf("%s%d",&s,&x) ; 
84         if(s[ 0 ]=='C') 
85             updata( IN[ x ] ) ; 
86         if(s[ 0 ]=='Q') 
87         {
88             ans = -query( IN[x]-1 ) ; 
89             ans+=query(OUT[x]) ; 
90             printf("%d
",ans) ; 
91         } 
92     }  
93     return 0 ; 
94 }