Propagating tree

## 题目描述 很久以前，有一棵神橡树(oak)，上面有$n$个节点，从$1$~$n$编号，由$n-1$条边相连。它的根是$1$号节点。 这棵橡树每个点都有一个权值，你需要完成这两种操作： $1$ $u$ $val$ 表示给$u$节点的权值增加$val$ $2$ $u$ 表示查询$u$节点的权值 但是这不是普通的橡树，它是神橡树。 所以它还有个神奇的性质：当某个节点的权值增加$val$时，它的子节点权值都增加$-val$，它子节点的子节点权值增加$-(-val)$...... 如此一直进行到树的底部。 ## 输入输出格式 ### 输入格式： 第一行两个正整数$n,m$，表示节点数量和操作数量。 第二行$n$个正整数$a_i$，依次表示每个节点的权值。 接下来$n-1$行，每行两个正整数$u,v$，表示$u,v$之间有一条边相连。 最后$m$行，每行若干个正整数，表示一次操作。 ### 输出格式： 对于每次询问，输出一行一个整数表示答案。 ## 说明 ### 数据范围： $1\le n,m \le 2\times 10^5$ $1\le a_i,val \le 1000$ $1\le u,v \le n$

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 $ a_{i} $ . 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 $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ $ (1<=a_{i}<=1000) $ . Each of the next $ n–1 $ lines contains two integers $ v_{i} $ and $ u_{i} $ $ (1<=v_{i},u_{i}<=n) $ , meaning that there is an edge between nodes $ v_{i} $ and $ u_{i} $ . 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)