记录编号	352015	评测结果	AAAAAAAAAA
题目名称	新型武器	最终得分	100
用户昵称	Kulliu	是否通过	通过
代码语言	C++	运行时间	1.017 s
提交时间	2016-11-16 20:32:56	内存使用	120.48 MiB

#include <iostream>
#include <cstdio> 
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 3e5 + 1;

#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	
	while (not is_num(tmp)) tmp = getchar();
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return res;
}


int a[maxn];
int tot_v[93][maxn];
int v[maxn];
int sn, n, q;

int dfn[maxn], nfd[maxn], end[maxn], tcnt;
int de[maxn], belong[maxn];
int deg[maxn], root;
int mx_de;

struct Edge {
	int to, ne;
	Edge() {}
	Edge(int to_, int ne_) { to = to_, ne = ne_; }
} e[maxn];
int head[maxn], ecnt;
inline void add_edge(int fr, int to) {
	e[++ecnt] = Edge(to, head[fr]), head[fr] = ecnt;
	deg[to]++;
}

void dfs(int now, int fa) {
	dfn[now] = ++tcnt;
	nfd[tcnt] = now;
	mx_de = max(mx_de, de[now]); 
	
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if (to == fa) continue;
		
		de[to] = de[now] + 1;
		dfs(to, now);
	}
	
	end[now] = tcnt;
}

inline void modify(int tar, int to) {
	int outree = dfn[tar];
	int ori = v[outree];
	
	tot_v[belong[outree]][de[tar]] += to - ori;
	v[outree] = to;
} 

int v_tmp[maxn];

inline int query(int tar, int deep) {
	if (deep >= n) return 0;
	
	int ans = 0;
	int l = dfn[tar], r = end[tar], top;
	int bl = belong[l], br = belong[r];
	
	if (bl == br) {
		for (int i = l ; i <= r; i++) if (de[nfd[i]] == deep) ans += v[i];
		return ans;
	} 
	
	top = bl * sn;
	if (l != top - sn + 1) {
		for (int i = l; i <= top; i++) if (de[nfd[i]] == deep) ans += v[i];
		bl++;
	}
	top = br * sn;
	if (r != top) {
		for (int i = top - sn + 1; i <= r; i++) if (de[nfd[i]] == deep) ans += v[i];
		br--;
	}
	for (int i = bl; i <= br; i++) ans += tot_v[i][deep];
	
	return ans;
}

inline void init() {
	for (int i = 1; i <= n; i++) if (not deg[i]) root = i;
	de[root] = 1;
	dfs(root, 0);
	for (int i = 1; i <= n; i++) v[dfn[i]] = a[i];
	
	if (n >= 3e5) sn = 3333;
	else sn = sqrt(n);
	int nblk = 1, cnt = 0;
	
	for (int i = 1; i <= n; i++) {
		tot_v[nblk][de[nfd[i]]] += v[i];
		belong[i] = nblk;
		
		if (++cnt == sn) cnt = 0, nblk++; 
	}
}

inline void read() {
	n = get_num();
	for (int i = 1; i <= n; i++) a[i] = get_num();
	for (int i = 1; i <= n - 1; i++) {
		int fr = get_num(), to = get_num();
		add_edge(fr, to);
	}
}
inline void solve() {
	q = get_num();
	int han, u, t;
	
	for (int i = 1; i <= q; i++) {
		han = get_num();
		u = get_num(), t = get_num();
		
		if (han == 1) modify(u, t);
		else printf("%d\n", query(u, de[u] + t));
	}
}

int main() {
	freopen("newweapon.in", "r", stdin); 
	freopen("newweapon.out", "w", stdout); 
	read();
	init();
	solve();
	return 0;
}