首页 > 代码库 > CodeForces 383C Propagating tree

CodeForces 383C Propagating tree

Propagating tree

Time Limit: 2000ms
Memory Limit: 262144KB
This problem will be judged on CodeForces. Original ID: 383C
64-bit integer IO format: %I64d      Java class name: (Any)
 
Iahub likes trees very much. Recently he discovered an interesting tree named propagating tree. The tree consists of n nodes numbered from 1 to n, each node i having an initial value ai. The root of the tree is node 1.

 

This tree has a special property: when a value val is added to a value of node i, the value -val is added to values of all the children of node i. Note that when you add value -val to a child of node i, you also add -(-val) to all children of the child of node i and so on. Look an example explanation to understand better how it works.

This tree supports two types of queries:

  • "x val" — val is added to the value of node x;
  • "x" — print the current value of node x.

In order to help Iahub understand the tree better, you must answer m queries of the preceding type.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 200000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000). Each of the next n–1 lines contains two integers viand ui (1 ≤ vi, ui ≤ n), meaning that there is an edge between nodes vi and ui.

Each of the next m lines contains a query in the format described above. It is guaranteed that the following constraints hold for all queries: 1 ≤ x ≤ n, 1 ≤ val ≤ 1000.

 

Output

For each query of type two (print the value of node x) you must print the answer to the query on a separate line. The queries must be answered in the order given in the input.

 

Sample Input

Input
5 5
1 2 1 1 2
1 2
1 3
2 4
2 5
1 2 3
1 1 2
2 1
2 2
2 4
Output
3
3
0

Hint

The values of the nodes are [1, 2, 1, 1, 2] at the beginning.

Then value 3 is added to node 2. It propagates and value -3 is added to it‘s sons, node 4 and node 5. Then it cannot propagate any more. So the values of the nodes are [1, 5, 1,  - 2,  - 1].

Then value 2 is added to node 1. It propagates and value -2 is added to it‘s sons, node 2 and node 3. From node 2 it propagates again, adding value 2 to it‘s sons, node 4 and node 5. Node 3 has no sons, so it cannot propagate from there. The values of the nodes are [3, 3,  - 1, 0, 1].

You can see all the definitions about the tree at the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)

 

Source

Codeforces Round #225 (Div. 1)
 
解题:此题有点坑,建两棵树一颗奇树,一颗偶树,奇数层节点奇树加,偶树减,偶数层节点,偶树加,奇树减。。。
 
  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cmath>  5 #include <algorithm>  6 #include <climits>  7 #include <vector>  8 #include <queue>  9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 300010; 18 struct node { 19     int lt,rt,val; 20 }; 21 struct arc{ 22     int to,next; 23     arc(int x = 0,int y = -1){ 24         to = x; 25         next = y; 26     } 27 }; 28 node tree[2][maxn<<2]; 29 arc e[maxn<<2]; 30 int head[maxn],lt[maxn],rt[maxn],val[maxn],d[maxn],idx,tot,n,m; 31 void add(int u,int v){ 32     e[tot] = arc(v,head[u]); 33     head[u] = tot++; 34 } 35 void dfs(int u,int fa){ 36     lt[u] = ++idx; 37     d[u] = d[fa]+1; 38     for(int i = head[u]; ~i; i = e[i].next){ 39         if(e[i].to == fa) continue; 40         dfs(e[i].to,u); 41     } 42     rt[u] = idx; 43 } 44 void build(int lt,int rt,int v) { 45     tree[0][v].lt = tree[1][v].lt = lt; 46     tree[0][v].rt = tree[1][v].rt = rt; 47     tree[0][v].val = tree[1][v].val = 0; 48     if(lt == rt) return; 49     int mid = (lt + rt)>>1; 50     build(lt,mid,v<<1); 51     build(mid+1,rt,v<<1|1); 52 } 53 void pushdown(int v,int o) { 54     if(tree[o][v].val) { 55         tree[o][v<<1].val += tree[o][v].val; 56         tree[o][v<<1|1].val += tree[o][v].val; 57         tree[o][v].val = 0; 58     } 59 } 60 void update(int lt,int rt,int v,int val,int o) { 61     if(tree[o][v].lt >= lt && tree[o][v].rt <= rt) { 62         tree[o][v].val += val; 63         return; 64     } 65     pushdown(v,o); 66     if(lt <= tree[o][v<<1].rt) update(lt,rt,v<<1,val,o); 67     if(rt >= tree[o][v<<1|1].lt) update(lt,rt,v<<1|1,val,o); 68 } 69 int query(int p,int v,int o){ 70     if(tree[o][v].lt == tree[o][v].rt) 71         return tree[o][v].val; 72     pushdown(v,o); 73     if(p <= tree[o][v<<1].rt) return query(p,v<<1,o); 74     if(p >= tree[o][v<<1|1].lt) return query(p,v<<1|1,o); 75 } 76 int main() { 77     int u,v,op; 78     while(~scanf("%d %d",&n,&m)){ 79         memset(head,-1,sizeof(head)); 80         idx = tot = 0; 81         for(int i = 1; i <= n; ++i) 82             scanf("%d",val+i); 83         for(int i = 1; i < n; ++i){ 84             scanf("%d %d",&u,&v); 85             add(u,v); 86             add(v,u); 87         } 88         build(1,n,1); 89         d[0] = 0; 90         dfs(1,0); 91         for(int i = 0; i < m; ++i){ 92             scanf("%d",&op); 93             if(op == 1){ 94                 scanf("%d %d",&u,&v); 95                 update(lt[u],rt[u],1,v,d[u]&1); 96                 if(lt[u] < rt[u]) update(lt[u]+1,rt[u],1,-v,(~d[u])&1); 97             }else{ 98                 scanf("%d",&u); 99                 printf("%d\n",val[u]+query(lt[u],1,d[u]&1));100             }101         }102     }103     return 0;104 }
View Code

 

CodeForces 383C Propagating tree