bzoj4034

//bzoj4034
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>typedef long long ll;typedef const int cint;typedef const long long cll;template <typename tp>inline void readln(tp &x) {	register char ch; register bool nega;	x = nega = 0;	for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) nega |= (ch == '-');	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';	if (nega) x = -x;}class SegTree {PRivate:	struct SegTNode {		int l, r;		ll sum, tag;		SegTNode() {			sum = tag = 0;		}	}tr[100005 << 2];	#define mid ((l + r) >> 1)	void Build(cint &k, cint &l, cint &r) {		tr[k].l = l, tr[k].r = r;		if (l == r) return;		Build(k << 1, l, mid);		Build(k << 1 | 1, mid + 1, r);	}	inline void DownTag(cint &k) {		tr[k << 1].tag += tr[k].tag;		tr[k << 1].sum += tr[k].tag * (tr[k << 1].r - tr[k << 1].l + 1ll);		tr[k << 1 | 1].tag += tr[k].tag;		tr[k << 1 | 1].sum += tr[k].tag * (tr[k << 1 | 1].r - tr[k << 1 | 1].l + 1ll);		tr[k].tag = 0;	}	void Add(cint &k, cint &L, cint &R, cll &x) {		int l = tr[k].l, r = tr[k].r;		if (L <= l && r <= R) {			tr[k].tag += x;			tr[k].sum += x * (r - l + 1ll);			return;		}		if (tr[k].tag) DownTag(k);		if (L <= mid) Add(k << 1, L, R, x);		if (mid < R) Add(k << 1 | 1, L, R, x);		tr[k].sum = tr[k << 1].sum + tr[k << 1 | 1].sum;	}	ll Query(cint &k, cint &L, cint &R) {		int l = tr[k].l, r = tr[k].r;		if (L <= l && r <= R) return tr[k].sum;		if (tr[k].tag) DownTag(k);		ll ret = 0;		if (L <= mid) ret += Query(k << 1, L, R);		if (mid < R) ret += Query(k << 1 | 1, L, R);		return ret;	}	#undef midpublic:	inline void build(cint &l, cint &r) {		Build(1, l, r);	}	inline void add(cint &l, cint &r, cll &x) {		Add(1, l, r, x);	}	inline void add(cint &a, cll &x) {		Add(1, a, a, x);	}	inline ll query(cint &l, cint &r) {		return Query(1, l, r);	}}SegT;int n, m;int sz[100005], fa[100005], son[100005], top[100005], order[100005], tot = 0;std::vector<int> to[100005];#define next to[nowp][i]int DFS(cint &nowp) {	int tmp, maxson = 0; sz[nowp] = 1;	for (unsigned i = 0; i < to[nowp].size(); i++) {		if (next == fa[nowp]) continue;		fa[next] = nowp;		sz[nowp] += (tmp = DFS(next));		if (tmp > maxson) {			maxson = tmp; son[nowp] = next;		}	}	return sz[nowp];}void DFS2(cint &nowp, cint &Top) {	if (!nowp) return;	top[nowp] = Top; order[nowp] = ++tot;	DFS2(son[nowp], Top);	for (unsigned i = 0; i < to[nowp].size(); i++) {		if (next == fa[nowp] || next == son[nowp]) continue;		DFS2(next, next);	}}#undef nextinline ll Calc(int x) {	ll ret = 0;	while (top[x] != 1) {		ret += SegT.query(order[top[x]], order[x]);		x = fa[top[x]];	}	ret += SegT.query(1, order[x]);	return ret;}inline void Init() {	int u, v;	readln(n); readln(m);	ll w[n + 1];	for (int i = 1; i <= n; i++) readln(w[i]);	for (int i = 1; i < n; i++) {		readln(u); readln(v);		to[u].push_back(v);		to[v].push_back(u);	}	DFS(1);	DFS2(1, 1);	SegT.build(1, n);	for (int i = 1; i <= n; i++) SegT.add(order[i], w[i]);}inline void Solve() {	int opt, x; ll a;	while (m--) {		readln(opt); readln(x);		switch (opt) {			case 1:				readln(a);				SegT.add(order[x], a);				break;			case 2:				readln(a);				SegT.add(order[x], order[x] + sz[x] - 1, a);				break;			case 3:				printf("%I64d/n", Calc(x));		}	}}int main() {	Init(); Solve();		return 0;}