记录编号	352445	评测结果	AAAAAAAAAA
题目名称	新型武器	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	1.716 s
提交时间	2016-11-17 10:26:26	内存使用	15.19 MiB

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#define file(x) "newweapon." #x
//#define DBG
const int V = 3e5 + 10;
using std::vector;
using std::max;
vector<int> to[V], a[V];
inline int lowbit(int x) {return x&-x;}
int n, q, dfsclk, dep[V], dfn[V], sz[V], w[V], pos[V], be[V], b[V], mxdp;
int bif(int x, const vector<int>& tar) {
	int l = 0, r = tar.size() - 1;
	while (l < r) {
		int mid =  l + r >> 1;
		if (dfn[tar[mid]] >= x) r = mid;
		else l = mid + 1;
	}
	return dfn[tar[l]] >= x ? l : -1;
}
int bil(int x, const vector<int>& tar) {
	int l = 0, r = tar.size() - 1;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (dfn[tar[mid]] <= x) l = mid;
		else r = mid - 1;
	}
	return dfn[tar[l]] <= x ? l : -1;
}
void dfs(int u, int fa) {
	pos[u] = a[dep[u]].size();
	a[dep[u]].push_back(u);
	dfn[u] = ++dfsclk;
	sz[u] = 1;
	for (int i = 0, v; i < (int)to[u].size(); ++i) if ((v = to[u][i]) != fa) {
		dep[v] = dep[u] + 1;
		mxdp = max(mxdp, dep[v]);
		dfs(v, u);
		sz[u] += sz[v];
	}
}
inline void add(int p, int x) {
	for(;p <= n; p += lowbit(p)) b[p] += x;
}
inline int pre(int p) {
	if (!p) return 0;
	int s = 0;
	for (; p; p -= lowbit(p)) s += b[p];
	return s;
}
inline int sum(int l, int r) {return pre(r) - pre(l - 1);}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		to[u].push_back(v), to[v].push_back(u);
	}
	dfs(1, -1);
	be[0] = 1;
	for (int i = 0; i <= mxdp; i++) {
		if (i) be[i] = be[i - 1] + a[i - 1].size();
		for (int j = 0; j < a[i].size(); j++) add(be[i] + j, w[a[i][j]]);
#ifdef DBG
		printf("%d : ", i);
		for (int j = 0; j < a[i].size(); j++) printf("%d ", a[i][j]);
		printf("\n");
#endif
	}
	be[mxdp + 1] = be[mxdp] + a[mxdp].size();
	scanf("%d", &q);
	while (q--) {
		int t, u, v;
		scanf("%d%d%d", &t , &u, &v);
		if (t == 1) {
			int p  = be[dep[u]] + pos[u];
			add(p, -sum(p, p));
			add(p, v);
		}
		else {
			int tar = dep[u] + v;
			if (tar > mxdp) {
				puts("0");
				continue;
			}
			int l = bif(dfn[u], a[tar]), r = bil(dfn[u] + sz[u] - 1, a[tar]);
#ifdef DBG
			printf("a[%d] : %d %d\n", dep[u] + v, l, r);
#endif
			if (l == -1 || r == -1) printf("%d\n", 0);
			else printf("%d\n", sum(be[tar] + l, be[tar] + r));
		}
	}
}