Codeforces Round #225 (Div. 1) C-Propagating tree （DFS序+线段树/树状数组）

题目链接：

http://codeforces.com/problemset/problem/383/C

题意：

给出一颗有n个节点，且1为根节点的树，每个节点有它的权值，现在进行m次操作，操作分为添加和查询，当一个节点的权值添加v，则它的孩子节点的权值要添加-v，它的孩子的孩子节点+v, 以此类推。

思路：

来自： http://blog.csdn.net/qq978874169/article/details/51519719

DFS标号后，按照深度分出奇偶层，当奇数（偶数）层+v时，对应偶数（奇数）层-v，两个线段树跑一跑就好。

dfs序是把树压下去，变成一条直线，这样连续的一段直线就是一颗子树，而我们每次更新就是更新的（L[x],R[x]）这段。

维护两颗线段树，一颗代表奇数层，一颗对应偶数层，每次操作都可能给相应的层加或者减去，因为每次操作的树可能在奇数层上也可能在偶数层上。

查询就是查询到叶子节点，返回这个叶子对应的奇数或者偶数层的数。

树状数组也可以做，更新是对L[x]~最后更新一次+y，再对R[x]+1~最后更新一次-y【更新回来】，这样就只更新了(L[x],R[x])

对于查询x，是查询1~L[x],也就是这个点的所有祖先对x的影响，求和就是答案了。

代码：

线段树：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e5+10;
17 
18 vector<int> node[maxn];
19 int val[maxn],n,m;
20 int L[maxn],R[maxn],flag[maxn],lazy[2][maxn<<2],tot;
21 
22 void dfs(int u,int fa,int f){
23     L[u] = ++tot;
24     flag[u] = f;
25     for(int i=0; i<(int)node[u].size(); i++){
26         int v = node[u][i];
27         if(fa == v) continue;
28         dfs(v,u,f^1);
29     }
30     R[u] = tot;
31 }
32 
33 void push_down(int rt){
34     if(lazy[0][rt]){
35         lazy[0][rt<<1] += lazy[0][rt];
36         lazy[0][rt<<1|1] += lazy[0][rt];
37     }
38     if(lazy[1][rt]){
39         lazy[1][rt<<1] += lazy[1][rt];
40         lazy[1][rt<<1|1] += lazy[1][rt];
41     }
42     lazy[0][rt] = lazy[1][rt] = 0;
43 }
44 
45 void update(int l,int r,int rt,int ql,int qr,int f,int val){
46     if(ql<=l && r<=qr) {
47         lazy[f][rt] += val; lazy[f^1][rt] -= val;
48         return ;
49     }
50     push_down(rt);
51     int mid = (l+r)/2;
52     if(ql<=mid) update(l,mid,rt<<1,ql,qr,f,val);
53     if(mid<qr) update(mid+1,r,rt<<1|1,ql,qr,f,val);
54 }
55 
56 int query(int l,int r,int rt,int f,int p){
57     if(l == r) return lazy[f][rt];
58     push_down(rt);
59     int mid = (l+r)/2;
60     if(p <= mid) query(l,mid,rt<<1,f,p);
61     else query(mid+1,r,rt<<1|1,f,p);
62 }
63 
64 int main(){
65     cin >> n >> m;
66     for(int i=1; i<=n; i++)
67         cin >> val[i];
68     for(int i=1; i<n; i++){
69         int x,y; cin>>x>>y;
70         node[x].push_back(y);
71         node[y].push_back(x);
72     }
73 
74     tot = 0;
75     dfs(1,-1,0);
76 
77     for(int i=0; i<m; i++){
78         int op,x,y; cin>>op>>x;
79         if(op==1){
80             cin >> y;
81             update(1,n,1,L[x],R[x],flag[x],y);
82         }else{
83             printf("%d
",val[x]+query(1,n,1,flag[x],L[x]));
84         }
85     }
86 
87     return 0;
88 }

树状数组：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e5+10;
17 
18 int n,m;
19 vector<int> node[maxn];
20 int tot,L[maxn],R[maxn],flag[maxn],val[maxn];
21 int lazy[2][maxn<<2];
22 
23 void dfs(int u,int fa,int f){
24     L[u] = ++tot;
25     flag[u] = f;
26     for(int i=0; i<(int)node[u].size(); i++){
27         int v = node[u][i];
28         if(v == fa) continue;
29         dfs(v,u,f^1);
30     }
31     R[u] = tot;
32 }
33 
34 void add(int x,int f,int val){
35     while(x<=n){
36         lazy[f][x] += val;
37         lazy[f^1][x] -= val;
38         x += x&-x;
39     }
40 }
41 
42 int que(int x,int f){
43     int res = 0;
44     while(x){
45         res += lazy[f][x];
46         x -= x&-x;
47     }
48     return res;
49 }
50 
51 int main(){
52     cin >> n >> m;
53     for(int i=1; i<=n; i++)
54         cin >> val[i];
55     for(int i=1; i<n; i++){
56         int x,y; cin>>x>>y;
57         node[x].push_back(y);
58         node[y].push_back(x);
59     }
60     tot = 0;
61     dfs(1,-1,0);
62 
63     for(int i=0; i<m; i++){
64         int op,x,y;
65         cin >> op >> x;
66         if(op == 1){
67             cin >> y;
68             add(L[x],flag[x],y);
69             add(R[x]+1,flag[x],-y);
70         }else{
71             printf("%d
",val[x]+que(L[x],flag[x]));
72         }
73     }
74 
75     return 0;
76 }