POJ 3321 Apple Tree (树状数组+dfs序)

给你n个点，n-1条边，1为根节点。给你m条操作，C操作是将x点变反(1变0，0变1)，Q操作是询问x节点以及它子树的值之和。初始所有的节点为1。

用DFS序的方法将以1为根节点DFS遍历所有的节点，L[i]表示i点出现的最早的时间戳，R[i]表示i点出现的最晚的时间戳，每个节点出现两次。

所以要是查询 i 及它子树的值的和之话，只要用树状数组查询L[i]~R[i]之间的值然后除以2，复杂度log(n)。改变操作的话，只要改变下标为L[i]以及R[i]上的值就可以了。

类似的题目有HDU3974，不过是线段树成段更新，也是用DFS序的方法写的。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <vector>
 5 using namespace std;
 6 const int MAXN = 2e5 + 5;
 7 const int INF = 1e9;
 8 int head[MAXN] , n , m , cnt , L[MAXN] , R[MAXN] , bit[MAXN * 2] , dfn , a[MAXN];
 9 //a数组表示每个元素的值
10 struct data {
11     int next , to;
12 }edge[MAXN * 2];
13 
14 inline void add_edge(int u , int v) {
15     edge[cnt].next = head[u];
16     edge[cnt].to = v;
17     head[u] = cnt++;
18 }
19 
20 void dfs(int u , int par) {
21     L[u] = ++dfn;
22     for(int i = head[u] ; ~i ; i = edge[i].next) {
23         int v = edge[i].to;
24         if(v == par)
25             continue;
26         dfs(v , u);
27     }
28     R[u] = ++dfn;
29 }
30 
31 inline void add(int i , int x) {
32     for( ; i <= dfn ; i += (i & -i))
33         bit[i] += x;
34 }
35 
36 int sum(int i) {
37     int s = 0;
38     for( ; i >= 1 ; i -= (i & -i))
39         s += bit[i];
40     return s;
41 }
42 
43 int main()
44 {
45     int u , v;
46     char q[5];
47     while(~scanf("%d" , &n)) {
48         memset(head , -1 , sizeof(head));
49         memset(bit , 0 , sizeof(bit));
50         memset(a , 0 , sizeof(a));
51         cnt = dfn = 0;
52         for(int i = 1 ; i < n ; i++) {
53             scanf("%d %d" , &u , &v);
54             add_edge(u , v);
55             add_edge(v , u);
56         }
57         dfs(1 , -1);
58         scanf("%d" , &m);
59         while(m--) {
60             scanf("%s %d" , q , &u);
61             if(q[0] == 'Q') {
62                 printf("%d
" , ((R[u] - L[u] + 1) - (sum(R[u]) - sum(L[u] - 1))) / 2); //除2因为dfs序中 每个点出现2次
63             }
64             else {
65                 if(a[u]) {
66                     add(L[u] , -1);
67                     add(R[u] , -1);
68                     a[u] = 0;
69                 }
70                 else {
71                     add(L[u] , 1);
72                     add(R[u] , 1);
73                     a[u] = 1;
74                 }
75             }
76         }
77     }
78 }