https://www.codechef.com/problems/IITK1P10
大概是：修改点值，求子树节点为0有多少个，
DFS序后,BIT 询问，修改
1 #include<bits/stdc++.h>
2
3 using namespace std;
4 typedef long long ll;
5
6 #define N 223456
7 ll val[N];
8 int l[N],r[N];
9 int t= 1;
10 int f[N];
11 int lowbit( int x)
12 {
13 return x&-x;
14 }
15 void update( int x, int v)
16 {
17 while (x<N)
18 {
19 f[x]+=v;
20 x+=lowbit(x);
21 }
22 }
23 ll query( int x)
24 {
25 ll s= 0;
26 while (x)
27 {
28 s+=f[x];
29 x-=lowbit(x);
30 }
31 return s;
32 }
33 vector< int>mp[N];
34 void dfs( int u, int pre)
35 {
36 l[u]=t++;
37 for ( int i= 0;i<mp[u].size();i++)
38 {
39 int v=mp[u][i];
40 if (v==pre) continue;
41 dfs(v,u);
42 }
43 r[u]=t- 1;
44 }
45
46
47 int main()
48 {
49 int n,Q;
50 scanf( " %d%d ",&n,&Q);
51 for ( int i= 1;i<n;i++)
52 {
53 int x,y;
54 scanf( " %d%d ",&x,&y);
55 mp[x].push_back(y);
56 mp[y].push_back(x);
57 }
58 dfs( 1, 0);
59 for ( int i= 1;i<=n;i++)
60 {
61 scanf( " %d ",&val[i]);
62 if (val[i]== 0) update(l[i], 1);
63 }
64 while (Q--)
65 {
66 char s[ 4];
67 scanf( " %s ",s);
68 if (s[ 0]== ' U ')
69 {
70 int u,v;
71 scanf( " %d%d ",&u,&v);
72 if (val[u]== 0) update(l[u],- 1);
73 val[u]+=v;
74 if (val[u]== 0) update(l[u], 1);
75 } else
76 {
77 int x;
78 scanf( " %d ",&x);
79 int ans=query(r[x])-query(l[x]- 1);
80 printf( " %d\n ",ans);
81 }
82 }
83 return 0;
84 }
2
3 using namespace std;
4 typedef long long ll;
5
6 #define N 223456
7 ll val[N];
8 int l[N],r[N];
9 int t= 1;
10 int f[N];
11 int lowbit( int x)
12 {
13 return x&-x;
14 }
15 void update( int x, int v)
16 {
17 while (x<N)
18 {
19 f[x]+=v;
20 x+=lowbit(x);
21 }
22 }
23 ll query( int x)
24 {
25 ll s= 0;
26 while (x)
27 {
28 s+=f[x];
29 x-=lowbit(x);
30 }
31 return s;
32 }
33 vector< int>mp[N];
34 void dfs( int u, int pre)
35 {
36 l[u]=t++;
37 for ( int i= 0;i<mp[u].size();i++)
38 {
39 int v=mp[u][i];
40 if (v==pre) continue;
41 dfs(v,u);
42 }
43 r[u]=t- 1;
44 }
45
46
47 int main()
48 {
49 int n,Q;
50 scanf( " %d%d ",&n,&Q);
51 for ( int i= 1;i<n;i++)
52 {
53 int x,y;
54 scanf( " %d%d ",&x,&y);
55 mp[x].push_back(y);
56 mp[y].push_back(x);
57 }
58 dfs( 1, 0);
59 for ( int i= 1;i<=n;i++)
60 {
61 scanf( " %d ",&val[i]);
62 if (val[i]== 0) update(l[i], 1);
63 }
64 while (Q--)
65 {
66 char s[ 4];
67 scanf( " %s ",s);
68 if (s[ 0]== ' U ')
69 {
70 int u,v;
71 scanf( " %d%d ",&u,&v);
72 if (val[u]== 0) update(l[u],- 1);
73 val[u]+=v;
74 if (val[u]== 0) update(l[u], 1);
75 } else
76 {
77 int x;
78 scanf( " %d ",&x);
79 int ans=query(r[x])-query(l[x]- 1);
80 printf( " %d\n ",ans);
81 }
82 }
83 return 0;
84 }