Propagating tree
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 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)
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.
class BIT:
    """"""

    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def get_val(self, i):
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def add(self, i, j, val):
        self._add(j, val)
        self._add(i, -val)
from collections import deque
import sys
input = sys.stdin.readline

def eular_tour(tree: list, root: int):
    """"""
    n = len(tree)
    res = []
    begin = [-1] * n
    end = [-1] * n
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        end[pos] = len(res)
        if begin[pos] == -1:
            begin[pos] = len(res) - 1
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)
    return (res, begin, end)
(n, q) = map(int, input().split())
init_cost = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n - 1)]
query = [list(map(int, input().split())) for i in range(q)]
tree = [[] for i in range(n)]
for i in range(n - 1):
    (a, b) = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
(res, begin, end) = eular_tour(tree, 0)
even_res = []
odd_res = []
for i in range(len(res)):
    if i % 2 == 0:
        even_res.append(res[i])
    else:
        odd_res.append(res[i])
even_bit = BIT(len(even_res))
odd_bit = BIT(len(odd_res))
for i in range(q):
    if query[i][0] == 1:
        (_, pos, cost) = query[i]
        pos -= 1
        if begin[pos] % 2 == 0:
            even_bit.add(begin[pos] // 2, (end[pos] + 1) // 2, cost)
            odd_bit.add(begin[pos] // 2, end[pos] // 2, -cost)
        else:
            odd_bit.add(begin[pos] // 2, end[pos] // 2, cost)
            even_bit.add((begin[pos] + 1) // 2, end[pos] // 2, -cost)
    else:
        (_, pos) = query[i]
        pos -= 1
        if begin[pos] % 2 == 0:
            ans = even_bit.get_val(begin[pos] // 2)
        else:
            ans = odd_bit.get_val(begin[pos] // 2)
        print(ans + init_cost[pos])
import sys
readline = sys.stdin.readline

class Dual_Segment_Tree:

    def __init__(self, N, f_act, e_act, operate, lst):
        self.N = N
        self.f_act = f_act
        self.e_act = e_act
        self.operate = operate
        self.lst = [None] * self.N
        for (i, x) in enumerate(lst):
            self.lst[i] = x
        self.segment_tree_act = [self.e_act] * (self.N + self.N)

    def __getitem__(self, i):
        if type(i) is int:
            if -self.N <= i < 0:
                i += self.N * 2
            elif 0 <= i < self.N:
                i += self.N
            else:
                raise IndexError('list index out of range')
            self.Propagate_Above(i)
            return self.Operate_At(i)
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None or a < -self.N:
                a = 0
            elif self.N <= a:
                a = self.N
            elif a < 0:
                a += self.N
            if b == None or self.N <= b:
                b = self.N
            elif b < -self.N:
                b = 0
            elif b < 0:
                b += self.N
            return self.lst[slice(a, b, c)]

    def Operate_At(self, i):
        return self.operate(self.lst[i - self.N], self.segment_tree_act[i])

    def Propagate_At(self, i):
        self.segment_tree_act[i << 1] = self.f_act(self.segment_tree_act[i << 1], self.segment_tree_act[i])
        self.segment_tree_act[i << 1 | 1] = self.f_act(self.segment_tree_act[i << 1 | 1], self.segment_tree_act[i])
        self.segment_tree_act[i] = self.e_act

    def Propagate_Above(self, i):
        H = i.bit_length() - 1
        for h in range(H, 0, -1):
            self.Propagate_At(i >> h)

    def Operate_Range(self, a, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.Propagate_Above(L0)
        self.Propagate_Above(R0)
        while L < R:
            if L & 1:
                self.segment_tree_act[L] = self.f_act(self.segment_tree_act[L], a)
                L += 1
            if R & 1:
                R -= 1
                self.segment_tree_act[R] = self.f_act(self.segment_tree_act[R], a)
            L >>= 1
            R >>= 1

    def Update(self):
        for i in range(1, self.N):
            self.Propagate_At(i)
            self.segment_tree_act[i] = self.e_act

    def __str__(self):
        import copy
        segment_tree_act = copy.deepcopy(self.segment_tree_act)
        for i in range(1, self.N):
            segment_tree_act[i << 1] = self.f_act(segment_tree_act[i << 1], segment_tree_act[i])
            segment_tree_act[i << 1 | 1] = self.f_act(segment_tree_act[i << 1 | 1], segment_tree_act[i])
            segment_tree_act[i] = self.e_act
            segment_tree_act[i] = self.e_act
        return '[' + ', '.join(map(str, [self.operate(x, a) for (x, a) in zip(self.lst, segment_tree_act[self.N:])])) + ']'

class Graph:

    def __init__(self, V, edges=False, graph=False, directed=False, weighted=False, inf=float('inf')):
        self.V = V
        self.directed = directed
        self.weighted = weighted
        self.inf = inf
        if graph:
            self.graph = graph
            self.edges = []
            for i in range(self.V):
                if self.weighted:
                    for (j, d) in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j, d))
                else:
                    for j in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j))
        else:
            self.edges = edges
            self.graph = [[] for i in range(self.V)]
            if weighted:
                for (i, j, d) in self.edges:
                    self.graph[i].append((j, d))
                    if not self.directed:
                        self.graph[j].append((i, d))
            else:
                for (i, j) in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)

    def SIV_DFS(self, s, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, lowlink=False, parents=False, postorder=False, preorder=False, subtree_size=False, topological_sort=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if lowlink:
            order = [None] * self.V
            ll = [None] * self.V
            idx = 0
        if parents or cycle_detection or lowlink or subtree_size:
            ps = [None] * self.V
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        if subtree_size:
            ss = [1] * self.V
        if unweighted_dist or bipartite_graph:
            uwd = [self.inf] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [self.inf] * self.V
            wd[s] = 0
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if lowlink:
                    order[x] = idx
                    ll[x] = idx
                    idx += 1
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
                        if parents or cycle_detection or lowlink or subtree_size:
                            ps[y] = x
                        if unweighted_dist or bipartite_graph:
                            uwd[y] = uwd[x] + 1
                        if weighted_dist:
                            wd[y] = wd[x] + d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag = False
                            if cycle_detection:
                                cd = (y, x)
            elif not finished[x]:
                finished[x] = True
                if euler_tour:
                    et.append(~x)
                if lowlink:
                    bl = True
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if ps[x] == y and bl:
                            bl = False
                            continue
                        ll[x] = min(ll[x], order[y])
                    if x != s:
                        ll[ps[x]] = min(ll[ps[x]], ll[x])
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if y == ps[x]:
                            continue
                        ss[x] += ss[y]
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (x, y) = tpl[:2] if self.weighted else tpl
                if uwd[x] == self.inf or uwd[y] == self.inf:
                    continue
                if not uwd[x] % 2 ^ uwd[y] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if uwd[x] == self.inf:
                        continue
                    bg[uwd[x] % 2].append(x)
        retu = ()
        if bipartite_graph:
            retu += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            retu += (cd,)
        if directed_acyclic:
            retu += (dag,)
        if euler_tour:
            retu += (et,)
        if linked_components:
            retu += (lc,)
        if lowlink:
            retu = (ll,)
        if parents:
            retu += (ps,)
        if postorder:
            retu += (post,)
        if preorder:
            retu += (pre,)
        if subtree_size:
            retu += (ss,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            retu += (tp_sort,)
        if unweighted_dist:
            retu += (uwd,)
        if weighted_dist:
            retu += (wd,)
        if len(retu) == 1:
            retu = retu[0]
        return retu
(N, M) = map(int, readline().split())
A = list(map(int, readline().split()))
edges = []
for _ in range(N - 1):
    (a, b) = map(int, readline().split())
    a -= 1
    b -= 1
    edges.append((a, b))
G = Graph(N, edges=edges)
(tour, size, depth) = G.SIV_DFS(0, preorder=True, subtree_size=True, unweighted_dist=True)
idx = [None] * N
for i in range(N):
    idx[tour[i]] = i
DST = Dual_Segment_Tree(N, lambda a, b: a + b, 0, lambda x, a: x + a, [0] * N)
for _ in range(M):
    query = map(int, readline().split())
    if next(query) == 1:
        (x, v) = query
        x -= 1
        i = idx[x]
        if depth[x] % 2:
            v = -v
        DST.Operate_Range(v, i, i + size[x])
    else:
        x = next(query)
        x -= 1
        i = idx[x]
        ans = A[x]
        if depth[x] % 2:
            ans -= DST[i]
        else:
            ans += DST[i]
        print(ans)
import collections
import sys
input = sys.stdin.readline

class FenwikTree:

    def construct(arr):
        n = len(arr)
        fenwick = [0] + arr[:]
        for i in range(n):
            j = i + (i & -i)
            if j < n:
                fenwick[j] += fenwick[i]
        return fenwick

    def getSum(arr, i):
        ans = 0
        while i > 0:
            ans += arr[i]
            i -= i & -i
        return ans

    def update(arr, i, val):
        while i < len(arr):
            arr[i] += val
            i += i & -i

def eular_path(adj, root, n):
    nodeToChild = collections.defaultdict(list)
    vis = set([root])
    stack = collections.deque([root])
    res = []
    begin = [-1] * n
    end = [-1] * n
    while stack:
        node = stack.pop()
        res.append(node)
        end[node - 1] = len(res) - 1
        if begin[node - 1] == -1:
            begin[node - 1] = len(res) - 1
        for child in adj[node]:
            if child not in vis:
                nodeToChild[node].append(child)
                vis.add(child)
                stack.append(node)
                stack.append(child)
    return (res, begin, end, nodeToChild)

def sol(arr, adj, qry, n):
    """"""
    (path, begin, end, nodeToChild) = eular_path(adj, 1, n)
    odd = [0] * (len(path[::2]) + 1)
    even = [0] * (len(path[1::2]) + 1)
    evenSet = set(path[1::2])
    for q in qry:
        if q[0] == 1:
            (_, node, cost) = q
            (leftIdx, rightIdx) = (begin[node - 1] // 2 + 1, end[node - 1] // 2 + 1)
            if node in evenSet:
                FenwikTree.update(even, leftIdx, cost)
                FenwikTree.update(even, rightIdx + 1, -cost)
                for child in nodeToChild[node]:
                    (leftIdx, rightIdx) = (begin[child - 1] // 2 + 1, end[child - 1] // 2 + 1)
                    FenwikTree.update(odd, leftIdx, -cost)
                    FenwikTree.update(odd, rightIdx + 1, cost)
            else:
                FenwikTree.update(odd, leftIdx, cost)
                FenwikTree.update(odd, rightIdx + 1, -cost)
                for child in nodeToChild[node]:
                    (leftIdx, rightIdx) = (begin[child - 1] // 2 + 1, end[child - 1] // 2 + 1)
                    FenwikTree.update(even, leftIdx, -cost)
                    FenwikTree.update(even, rightIdx + 1, cost)
        else:
            (_, node) = q
            idx = begin[node - 1] // 2 + 1
            if node in evenSet:
                print(FenwikTree.getSum(even, idx) + arr[node - 1])
            else:
                print(FenwikTree.getSum(odd, idx) + arr[node - 1])
t = 1
for _ in range(t):
    (n, m) = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    adj = collections.defaultdict(list)
    for _ in range(n - 1):
        (u, v) = list(map(int, input().split()))
        adj[u].append(v)
        adj[v].append(u)
    qry = []
    for _ in range(m):
        qry.append(list(map(int, input().split())))
    sol(arr, adj, qry, n)