Propagating tree
This problem will be judged on CodeForces. Original ID: 383C
64-bit integer IO format: %I64d Java class name: (Any)
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:
- "1 x val" — val is added to the value of node x;
- "2 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
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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
struct node {
int lt,rt,val;
};
struct arc{
int to,next;
arc(int x = ,int y = -){
to = x;
next = y;
}
};
node tree[][maxn<<];
arc e[maxn<<];
int head[maxn],lt[maxn],rt[maxn],val[maxn],d[maxn],idx,tot,n,m;
void add(int u,int v){
e[tot] = arc(v,head[u]);
head[u] = tot++;
}
void dfs(int u,int fa){
lt[u] = ++idx;
d[u] = d[fa]+;
for(int i = head[u]; ~i; i = e[i].next){
if(e[i].to == fa) continue;
dfs(e[i].to,u);
}
rt[u] = idx;
}
void build(int lt,int rt,int v) {
tree[][v].lt = tree[][v].lt = lt;
tree[][v].rt = tree[][v].rt = rt;
tree[][v].val = tree[][v].val = ;
if(lt == rt) return;
int mid = (lt + rt)>>;
build(lt,mid,v<<);
build(mid+,rt,v<<|);
}
void pushdown(int v,int o) {
if(tree[o][v].val) {
tree[o][v<<].val += tree[o][v].val;
tree[o][v<<|].val += tree[o][v].val;
tree[o][v].val = ;
}
}
void update(int lt,int rt,int v,int val,int o) {
if(tree[o][v].lt >= lt && tree[o][v].rt <= rt) {
tree[o][v].val += val;
return;
}
pushdown(v,o);
if(lt <= tree[o][v<<].rt) update(lt,rt,v<<,val,o);
if(rt >= tree[o][v<<|].lt) update(lt,rt,v<<|,val,o);
}
int query(int p,int v,int o){
if(tree[o][v].lt == tree[o][v].rt)
return tree[o][v].val;
pushdown(v,o);
if(p <= tree[o][v<<].rt) return query(p,v<<,o);
if(p >= tree[o][v<<|].lt) return query(p,v<<|,o);
}
int main() {
int u,v,op;
while(~scanf("%d %d",&n,&m)){
memset(head,-,sizeof(head));
idx = tot = ;
for(int i = ; i <= n; ++i)
scanf("%d",val+i);
for(int i = ; i < n; ++i){
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
build(,n,);
d[] = ;
dfs(,);
for(int i = ; i < m; ++i){
scanf("%d",&op);
if(op == ){
scanf("%d %d",&u,&v);
update(lt[u],rt[u],,v,d[u]&);
if(lt[u] < rt[u]) update(lt[u]+,rt[u],,-v,(~d[u])&);
}else{
scanf("%d",&u);
printf("%d\n",val[u]+query(lt[u],,d[u]&));
}
}
}
return ;
}
树状数组
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
vector<int>g[maxn];
int c[][maxn],val[maxn],d[maxn],L[maxn],R[maxn],clk,n,m;
void dfs(int u,int fa,int dep){
d[u] = dep;
L[u] = ++clk;
for(int i = g[u].size()-; i >= ; --i){
if(g[u][i] == fa) continue;
dfs(g[u][i],u,dep+);
}
R[u] = clk;
}
void update(int cur,int i,int val){
while(i < maxn){
c[cur][i] += val;
i += i&-i;
}
}
int sum(int cur,int i,int ret = ){
while(i > ){
ret += c[cur][i];
i -= i&-i;
}
return ret;
}
int main(){
int u,v,op,x;
while(~scanf("%d%d",&n,&m)){
for(int i = ; i <= n; ++i){
g[i].clear();
scanf("%d",val+i);
}
for(int i = ; i < n; ++i){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(,-,);
memset(c,,sizeof c);
while(m--){
scanf("%d%d",&op,&x);
if(op == ){
scanf("%d",&v);
update(d[x]&,L[x],v);
update(d[x]&,R[x]+,-v);
}else printf("%d\n",val[x] + sum(d[x]&,L[x]) - sum(~d[x]&,L[x]));
}
}
return ;
}