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.
def EulerTour(g, root):
    n = len(g)
    root = root
    g = g
    tank = [root]
    eulerTour = []
    left = [0] * n
    right = [-1] * n
    depth = [-1] * n
    parent = [-1] * n
    child = [[] for i in range(n)]
    eulerNum = -1
    de = -1
    while tank:
        v = tank.pop()
        if v >= 0:
            eulerNum += 1
            eulerTour.append(v)
            left[v] = eulerNum
            right[v] = eulerNum
            tank.append(~v)
            de += 1
            depth[v] = de
            for u in g[v]:
                if parent[v] == u:
                    continue
                tank.append(u)
                parent[u] = v
                child[v].append(u)
        else:
            de -= 1
            if ~v != root:
                eulerTour.append(parent[~v])
                eulerNum += 1
                right[parent[~v]] = eulerNum
    return (eulerTour, left, right, depth)

class BIT:

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

    def init(self, init_val):
        for (i, v) in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i, j):
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

class RangeAddBIT:

    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x * l)
        self.bit2.add(r, x * r)

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        return self.bit1._sum(i) * i + self.bit2._sum(i)

    def __str__(self):
        arr = [self.sum(i, i + 1) for i in range(self.n)]
        return str(arr)
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
edge = [[] for i in range(n)]
for i in range(n - 1):
    (u, v) = map(int, input().split())
    (u, v) = (u - 1, v - 1)
    edge[u].append(v)
    edge[v].append(u)
(et, left, right, depth) = EulerTour(edge, 0)
N = len(et)
bitEven = RangeAddBIT(N + 1)
bitOdd = RangeAddBIT(N + 1)
for i in range(m):
    temp = list(map(int, input().split()))
    if temp[0] == 1:
        (x, val) = temp[1:]
        x -= 1
        (l, r) = (left[x], right[x])
        if l % 2 == 0:
            bitEven.add(l, r + 1, val)
            bitOdd.add(l, r + 1, -val)
        else:
            bitEven.add(l, r + 1, -val)
            bitOdd.add(l, r + 1, val)
    else:
        x = temp[1]
        x -= 1
        l = left[x]
        if l % 2 == 0:
            ans = bitEven.sum(l, l + 1) + A[x]
        else:
            ans = bitOdd.sum(l, l + 1) + A[x]
        print(ans)
def EulerTour(g, root):
    n = len(g)
    root = root
    g = g
    tank = [root]
    eulerTour = []
    left = [0] * n
    right = [-1] * n
    depth = [-1] * n
    parent = [-1] * n
    child = [[] for i in range(n)]
    eulerNum = -1
    de = -1
    while tank:
        v = tank.pop()
        if v >= 0:
            eulerNum += 1
            eulerTour.append(v)
            left[v] = eulerNum
            right[v] = eulerNum
            tank.append(~v)
            de += 1
            depth[v] = de
            for u in g[v]:
                if parent[v] == u:
                    continue
                tank.append(u)
                parent[u] = v
                child[v].append(u)
        else:
            de -= 1
            if ~v != root:
                eulerTour.append(parent[~v])
                eulerNum += 1
                right[parent[~v]] = eulerNum
    return (eulerTour, left, right, depth)

class BIT:

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

    def init(self, init_val):
        for (i, v) in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i, j):
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

class RangeAddBIT:

    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x * l)
        self.bit2.add(r, x * r)

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        return self.bit1._sum(i) * i + self.bit2._sum(i)

    def __str__(self):
        arr = [self.sum(i, i + 1) for i in range(self.n)]
        return str(arr)
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
edge = [[] for i in range(n)]
for i in range(n - 1):
    (u, v) = map(int, input().split())
    (u, v) = (u - 1, v - 1)
    edge[u].append(v)
    edge[v].append(u)
(et, left, right, depth) = EulerTour(edge, 0)
N = len(et)
bitEven = RangeAddBIT(N + 1)
bitOdd = RangeAddBIT(N + 1)
for i in range(m):
    temp = list(map(int, input().split()))
    if temp[0] == 1:
        (x, val) = temp[1:]
        x -= 1
        (l, r) = (left[x], right[x])
        if depth[x] % 2 == 0:
            bitEven.add(l, r + 1, val)
            bitOdd.add(l, r + 1, -val)
        else:
            bitEven.add(l, r + 1, -val)
            bitOdd.add(l, r + 1, val)
    else:
        x = temp[1]
        x -= 1
        l = left[x]
        if depth[x] % 2 == 0:
            ans = bitEven.sum(l, l + 1) + A[x]
        else:
            ans = bitOdd.sum(l, l + 1) + A[x]
        print(ans)
from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
from random import randint, randrange
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
from math import ceil, floor, factorial, log10
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict
M = 1000000007
INF = 9223372036854775807
PI = 3.141592653589793
R = randrange(2, 1 << 32)

class SegmentTree:

    def __init__(self, data, default=0, func=lambda x, y: x + y):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

@bootstrap
def dfs(u, par, g, level, dfsarr, ind, parent):
    ind[u] = [level, len(dfsarr[level]), -1]
    dfsarr[level].append(u)
    parent[u] = par
    for v in g[u]:
        if v != par:
            yield dfs(v, u, g, level ^ 1, dfsarr, ind, parent)
    ind[u][2] = len(dfsarr[level])
    yield

def main():
    TestCases = 1
    for _ in range(TestCases):
        (n, qq) = [int(i) for i in input().split()]
        arr = [int(i) for i in input().split()]
        g = [[] for i in range(n)]
        for _ in range(n - 1):
            (u, v) = [int(i) - 1 for i in input().split()]
            g[u].append(v)
            g[v].append(u)
        dfsarr = [[], []]
        parent = [-1] * n
        ind = [[-1, -1, -1]] * n
        dfs(0, -1, g, 0, dfsarr, ind, parent)
        seg = [SegmentTree([0] * (len(i) + 1)) for i in dfsarr]
        for q in range(qq):
            que = [int(i) for i in input().split()]
            if que[0] == 1:
                (_, x, val) = que
                x -= 1
                (level, st, en) = ind[x]
                seg[level][st] += val
                seg[level][en] -= val
                for child in g[x]:
                    if child == parent[x]:
                        continue
                    (level, st, en) = ind[child]
                    seg[level][st] -= val
                    seg[level][en] += val
            else:
                (_, x) = que
                x -= 1
                (level, st, en) = ind[x]
                print(seg[level].query(0, st + 1) + arr[x])
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

def copy2d(lst):
    return [x[:] for x in lst]

def no_of_digits(num):
    return 0 if num <= 0 else int(log10(num)) + 1

def powm(num, power, mod=M):
    return pow(num, power, mod)

def isPowerOfTwo(x):
    return x and (not x & x - 1)

def LSB(num):
    """"""
    return num & -num

def MSB(num):
    """"""
    if num <= 0:
        return 0
    ans = 1
    num >>= 1
    while num:
        num >>= 1
        ans <<= 1
    return ans
LB = bisect_left
UB = bisect_right

def BS(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(x, y):
    return x * y // gcd(x, y)

class Wrapper(int):

    def __init__(self, x):
        int.__init__(x)

    def __hash__(self):
        return super(Wrapper, self).__hash__() ^ R
Int = lambda x: Wrapper(int(x))

class myDict:

    def __init__(self, func=int):
        self.RANDOM = R
        self.default = func
        self.dict = {}

    def __getitem__(self, key):
        myKey = self.RANDOM ^ key
        if myKey not in self.dict:
            self.dict[myKey] = self.default()
        return self.dict[myKey]

    def __setitem__(self, key, item):
        myKey = self.RANDOM ^ key
        self.dict[myKey] = item

    def __contains__(self, key):
        myKey = self.RANDOM ^ key
        return myKey in self.dict

    def __delitem__(self, key):
        myKey = self.RANDOM ^ key
        del self.dict[myKey]

    def keys(self):
        return [self.RANDOM ^ i for i in self.dict]
if not os.path.isdir('C:/users/acer'):
    BUFSIZE = 8192

    class FastIO(IOBase):
        newlines = 0

        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = 'x' in file.mode or 'r' not in file.mode
            self.write = self.buffer.write if self.writable else None

        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines = 0
            return self.buffer.read()

        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b'\n') + (not b)
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines -= 1
            return self.buffer.readline()

        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                (self.buffer.truncate(0), self.buffer.seek(0))

    class IOWrapper(IOBase):

        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda : self.buffer.read().decode('ascii')
            self.readline = lambda : self.buffer.readline().decode('ascii')

    def print(*args, **kwargs):
        """"""
        (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
        at_start = True
        for x in args:
            if not at_start:
                file.write(sep)
            file.write(str(x))
            at_start = False
        file.write(kwargs.pop('end', '\n'))
        if kwargs.pop('flush', False):
            file.flush()
    if sys.version_info[0] < 3:
        (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
    else:
        (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
    input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()