C. Propagating tree
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/383/problem/C
Description
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 vi and 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
Sample Output
3
3
0
HINT
题意
给出一颗有n个节点并一1为根节点的树，每个节点有它的权值，现在进行m次操作，操作分为添加和查询，当一个节点的权值添加val，则它的孩子节点的权值要添加-b。
题解：
dfs序+树状数组
分成两颗树做
http://blog.csdn.net/keshuai19940722/article/details/18967661
代码
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 2000001
#define mod 1000000007
#define eps 1e-9
int Num;
char CH[];
const int inf=0x3f3f3f3f;
inline ll read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} //************************************************************************************** struct node
{
int l,r,v,d;
}node[maxn];
int n,m;
vector<int> e[maxn];
int bit[][maxn];
int cnt;
void add(int x,int val,int *b)
{
while(x<=n*)
{
b[x]+=val;
x+=(x&(-x));
}
}
int get(int x,int *b)
{
int ans=;
while(x>)
{
ans+=b[x];
x-=(x&(-x));
}
return ans;
}
void dfs(int x,int fa,int d)
{
node[x].l=cnt++;
node[x].d=d;
for(int i=;i<e[x].size();i++)
{
if(e[x][i]==fa)
continue;
dfs(e[x][i],x,-d);
}
node[x].r=cnt++;
}
int main()
{
n=read(),m=read();
for(int i=;i<=n;i++)
node[i].v=read();
for(int i=;i<n;i++)
{
int a=read(),b=read();
e[a].push_back(b);
e[b].push_back(a);
}
cnt=;
dfs(,-,);
for(int i=;i<m;i++)
{
int op=read();
if(op==)
{
int a=read(),b=read();
add(node[a].l,b,bit[node[a].d]);
add(node[a].r+,-b,bit[node[a].d]);
}
else
{
int a=read();
printf("%d\n",node[a].v+get(node[a].l,bit[node[a].d])-get(node[a].l,bit[-node[a].d]));
}
}
}