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:
- "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.
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.
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.
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
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)
题意：n个结点的树，以1为根，可以往结点添加值，添加之后他的子孩子会添加负的该值，直到树的叶子结点为止。有询问和添加值的操作
思路：树状数组，先进行一遍dfs，把每个结点对应的孩子的区间l，r记录下来，然后进行树状数组的区间更新，询问的时候就计算1-l的和，因为这些都为该结点的父亲结点，然后开两个数组，一个作为正一个作为负。
代码：
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int N = 200005;
int n, m, num = 1, bit[2][2 * N];
struct Node {
int l, r, v, d;
}node[N];
vector<int> g[N];
void add(int x, int v, int *bit) {
while (x <= 2 * n) {
bit[x] += v;
x += (x&(-x));
}
}
int get(int x, int *bit) {
int ans = 0;
while (x > 0) {
ans += bit[x];
x -= (x&(-x));
}
return ans;
}
void dfs(int u, int fa, int d) {
node[u].l = num++; node[u].d = d;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa) continue;
dfs(v, u, 1 - d);
}
node[u].r = num++;
}
void init() {
scanf("%d%d", &n, &m);
int u, v;
for (int i = 1; i <= n; i++)
scanf("%d", &node[i].v);
for (int j = 0; j < n - 1; j++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, -1, 0);
}
void solve() {
int cz, a, b;
while (m--) {
scanf("%d", &cz);
if (cz == 1) {
scanf("%d%d", &a, &b);
add(node[a].l, b, bit[node[a].d]);
add(node[a].r + 1, -b, bit[node[a].d]);
}
else {
scanf("%d", &a);
printf("%d\n", node[a].v + get(node[a].l, bit[node[a].d]) - get(node[a].l, bit[1 - node[a].d]));
}
}
}
int main() {
init();
solve();
return 0;
}