记录编号	458716	评测结果	AAAAAAAAAA
题目名称	新型武器	最终得分	100
用户昵称	nfy_2002	是否通过	通过
代码语言	C++	运行时间	1.738 s
提交时间	2017-10-11 19:29:08	内存使用	24.35 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define RG register
#define IL inline
#define pi acos(-1.0)
#define ll long long
#define lson o*2
#define rson o*2+1
using namespace std;

struct date{
	int first,nxt,to;
};
date a[700000];
int num,n,q,ans=0;
int w[300005];
int b[300005];//bfs序列构成的
int bfn[300005],dfn[300005];
int bf=0,df=0;
int size[300005],deep[300005];
int tree[1500000];
int s[300005];
int beg[300005],en[300005];

void add(int l,int r){
	a[++num].to=r;
	a[num].nxt=a[l].first;
	a[l].first=num;
}

void bfs(){
	memset(deep,-1,sizeof(deep));
  int head=0,tail=1;
	s[tail]=1;
	deep[1]=0;
	bfn[1]=++bf;
	b[1]=1;
	beg[0]=en[0]=1;
	while(head<=tail){
		++head;
		int u=s[head];
		for(int i=a[u].first;i;i=a[i].nxt){
			int v=a[i].to;
			if(deep[v]==-1){
				 deep[v]=deep[u]+1;
				 bfn[v]=++bf;
				 b[bf]=v;
				 s[++tail]=v;
				 if(!beg[deep[v]]) beg[deep[v]]=bf;
				 en[deep[v]]=bf;
			}
		}
	}
}

void dfs(int u,int fa){
	size[u]=1;
	dfn[u]=++df;
	for(int i=a[u].first;i;i=a[i].nxt){
		int v=a[i].to;
		if(v==fa) continue;
		else{
			dfs(v,u);
			size[u]+=size[v];
		}
	}
}

void build(int l,int r,int o){
	if(l==r){
		tree[o]=w[b[l]];
		return;
	}
	int mid=(l+r)/2;
	if(l<=mid) build(l,mid,lson);
	if(r>mid) build(mid+1,r,rson);
	tree[o]=tree[lson]+tree[rson];
}

void update(int l,int r,int x,int zhi,int o){
	if(l==r){
		 tree[o]=zhi;
		 return;
	}
	int mid=(l+r)/2;
	if(x<=mid) update(l,mid,x,zhi,lson);
	else update(mid+1,r,x,zhi,rson);
	tree[o]=tree[lson]+tree[rson];
}

void ques(int l,int r,int L,int R,int o){
	if(l>=L&&r<=R){
		ans+=tree[o];
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid) ques(l,mid,L,R,lson);
	if(R>mid) ques(mid+1,r,L,R,rson);
}

int pre(int l,int r,int x){
	int ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(dfn[b[mid]]<x) l=mid+1;
		else ans=mid,r=mid-1;
	}
	return ans;
}

int low(int l,int r,int x){
	int ans=0;
	while(l<=r){
		 int mid=(l+r)/2;
		 if(dfn[b[mid]]<=x) ans=mid,l=mid+1;
		 else r=mid-1;
	}
	return ans;
}

int main(){
  freopen("newweapon.in","r",stdin);
	freopen("newweapon.out","w",stdout);
  scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	int l,r;
	for(int i=1;i<n;i++)
		scanf("%d%d",&l,&r),add(l,r),add(r,l);
	bfs();
	dfs(1,-1);
	build(1,n,1);
	scanf("%d",&q);
	int type,u,v;
	while(q--){
    scanf("%d%d%d",&type,&u,&v);
		if(type==1){
			 w[u]=v;
			 update(1,n,bfn[u],v,1);
		}
		else{
			int dep=deep[u]+v;
			int L=pre(beg[dep],en[dep],dfn[u]);
			int R=low(beg[dep],en[dep],dfn[u]+size[u]-1);
			if(L==0||R==0){
				printf("0\n");
				continue;
			}
      ans=0;
			ques(1,n,L,R,1);
			printf("%d\n",ans);
		}
	}
	return 0;
}