记录编号	461827	评测结果	AAAAAAAAAA
题目名称	新型武器	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.417 s
提交时间	2017-10-20 19:55:44	内存使用	76.99 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e;edge *n;
}*pre[300005];
inline void insert(int s,int e){
	edge *tmp(new edge);tmp->e=e;tmp->n=pre[s];pre[s]=tmp;
}
int n,q;
int w[300005];
int cnt,l[300005],r[300005],pos[300005],dep[300005];
inline void dfs(int u,int fa){
	l[u]=++cnt;pos[cnt]=u;
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e);
		if(e==fa)continue;
		dep[e]=dep[u]+1;
		dfs(e,u);
	}
	r[u]=cnt;
}
int root[300005],sum[6000005],lch[6000005],rch[6000005];
inline void pushup(int x){
	sum[x]=sum[lch[x]]+sum[rch[x]];
}
inline void update(int &x,int pos,int w,int l,int r){
	if(!x)x=++cnt;
	if(l==r){sum[x]=w;return;}
	int mid((l+r)>>1);
	if(pos<=mid)update(lch[x],pos,w,l,mid);
	else update(rch[x],pos,w,mid+1,r);
	pushup(x);
}
inline int query(int x,int ll,int rr,int l,int r){
	if(ll==l&&r==rr)return sum[x];
	int mid((l+r)>>1);
	if(rr<=mid)return query(lch[x],ll,rr,l,mid);
	if(mid<ll)return query(rch[x],ll,rr,mid+1,r);
	return query(lch[x],ll,mid,l,mid)+query(rch[x],mid+1,rr,mid+1,r);
}
int main(){
	freopen("newweapon.in","r",stdin);
	freopen("newweapon.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i)w[i]=read();
	for(int i=1;i<n;++i){
		int x(read()),y(read());
		insert(x,y);insert(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=n;++i)update(root[dep[i]],l[i],w[i],1,n);
	q=read();
	while(q--){
		int op(read()),x(read()),y(read());
		if(op==1)update(root[dep[x]],l[x],y,1,n);
		else printf("%d\n",query(root[dep[x]+y],l[x],r[x],1,n));
	}
}