记录编号	351467	评测结果	AAAAAAAAAA
题目名称	新型武器	最终得分	100
用户昵称	Riolu	是否通过	通过
代码语言	C++	运行时间	1.378 s
提交时间	2016-11-16 16:25:37	内存使用	7.74 MiB

/*=========================================*
  * Auther: Riolu
  * Time: 2016.11.16
  * ©Copyright 2016 Riolu. All Rights Reserved.
  *=========================================*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
//#include<cmath>
#include<string>
#include<cstring>
using namespace std;

typedef pair<int,int> P;
typedef long long ll;
typedef double db;
const int N =3e5+1;
int n,k;
//v 每个点的权，b bfs序列,df dfs序列,deth bfs序列中点的深度,posb 在b中的位置,de每个点的深度,
int v[N],b[N],df[N],deth[N],posb[N],posf[N],de[N];
vector<int> son[N];
int sd[N];//第一个深度出现位置
int head,end,num;
int Q(int rt,int c){
	int ans=0,i,l=son[rt].size();
	if(c==0)return v[rt];
	//cout<<de[rt]<<endl;
	//cout<<de[rt]+c<<endl;
	int frontd=sd[de[rt]+c],endd=sd[de[rt]+c+1]-1;
	int pos1=posf[rt],pos2=posf[b[posb[rt]+1]];
	if(deth[posb[rt]+1]!=de[rt])pos2=n+1;
	//cout<<frontd<<' '<<endd<<' '<<pos1<<' '<<pos2<<endl;
	for(i=frontd;i<=endd;i++){
		if(pos1<posf[b[i]]&&posf[b[i]]<pos2)
			ans+=v[b[i]];
	}
	return ans;
}
void bfs(){
	head=end=1;b[end++]=1;posb[1]=1;deth[1]=1;
	int t,i,j,l;
	while(head<end){
		t=b[head++];l=son[t].size();
		for(i=0;i<l;i++){
			deth[end]=de[son[t][i]];
			b[end]=son[t][i];
			posb[son[t][i]]=end++;
		}
	}
	//for(i=1;i<end;i++)cout<<b[i]<<' ';cout<<endl;
	//for(i=1;i<end;i++)cout<<posb[i]<<' ';cout<<endl;
	//for(i=1;i<end;i++)cout<<de[i]<<' ';cout<<endl;
}
void dfsf(int pos,int y){
	df[++num]=pos;posf[pos]=num;de[pos]=y;
	int i,l=son[pos].size();
	for(i=0;i<l;i++)dfsf(son[pos][i],y+1);
}
int read(){
	freopen("newweapon.in","r",stdin);
	freopen("newweapon.out","w",stdout);
	scanf("%d",&n);
	int i,fa,to,t,t1,t2;
	for(i=1;i<=n;i++)scanf("%d",&v[i]);
	for(i=1;i<n;i++){
		scanf("%d%d",&fa,&to);
		son[fa].push_back(to);
		}
	dfsf(1,1);
	bfs();
	sd[deth[n]+1]=n+1;
	for(i=end-1;i>=1;i--)sd[deth[i]]=i;
	//for(i=1;i<=6;i++)cout<<sd[i]<<' ';cout<<endl;
	//for(i=1;i<end;i++)cout<<df[i]<<' ';cout<<endl;
	//for(i=1;i<end;i++)cout<<posf[i]<<' ';cout<<endl;
	scanf("%d",&k);
	for(i=1;i<=k;i++){
		scanf("%d%d%d",&t,&t1,&t2);
		if(t==1)v[t1]=t2;
		else printf("%d\n",Q(t1,t2));
	}
	fclose(stdin);fclose(stdout);
}int R=read();int main(){;}