记录编号	351231	评测结果	AAAATTTTTT
题目名称	新型武器	最终得分	40
用户昵称	srO cwm Orz	是否通过	未通过
代码语言	C++	运行时间	6.005 s
提交时间	2016-11-16 12:14:46	内存使用	5.95 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
 
const int maxn = 300003;
vector<int> G[maxn];
int w[maxn];
int depth[maxn];
bool inq[maxn],vis[maxn];
int tot;
int n,q;
 
void bfs(){
	queue<int> q;
	q.push(1);inq[1]=1;
	while(!q.empty()){
		int u = q.front(); q.pop(); inq[u]=0;
		for(int i = 0; i < G[u].size(); i++){
			int to = G[u][i];
			if(!inq[to] && !depth[to]){
				depth[to] = depth[u]+1;//printf("%d %d\n",to,depth[to]);
				q.push(to);
				inq[to]=1;
			}
		}
	}
	depth[1]=0;
}
 
int sum;
int ndep;
 
void dfs(int fr){
	if(depth[fr] == ndep){
		sum += w[fr];
		return;
	}
	if(depth[fr] > ndep)return;
	for(int i = 0; i < G[fr].size(); i++){
		int to = G[fr][i];
		dfs(to);
	}
}
int main(){
	#ifndef DEBUG
		string FileName="newweapon";
		freopen((FileName+".in").c_str(),"r",stdin);
		freopen((FileName+".out").c_str(),"w",stdout);
	#endif
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)scanf("%d",&w[i]);
	for(int i = 1; i <= n-1; i++){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
	}
	bfs();
	scanf("%d",&q);
	for(int i = 0; i < q; i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a == 1){
			w[b] = c;
		}else{
			sum = 0;
			ndep = c+depth[b];
			dfs(b);
			printf("%d\n",sum);
		}
	}
}