记录编号	351306	评测结果	AWWWTTTTTT
题目名称	2551.新型武器	最终得分	10
用户昵称	jmisnal	是否通过	未通过
代码语言	C++	运行时间	6.091 s
提交时间	2016-11-16 14:13:24	内存使用	13.25 MiB

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#define ll long long
using namespace std;
int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
struct data{
	int to,next;
}e[650000];
int head[300100],cnt;
void insert(int u,int v)
{
//	cout<<u<<' '<<v<<endl;
	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
/*
struct abcd{
	int l,r,v;
}tr[300300];
*/
int hash[300300],ind;
int n,v[300300];
bool hav[300300];
queue<int>Q;
void bfs()
{
	Q.push(1);
	while(!Q.empty())
	{
		int now=Q.front();
		Q.pop();
	//	cout<<now<<' '<<ind<<endl;
		if(hav[now])continue;
		hav[now]=1;
		hash[now]=++ind;
		for(int i=head[now];i;i=e[i].next)
		{
			int to=e[i].to;
			if(hav[to])continue;
			
			Q.push( to );
		}
	}
}
int lowbit(int x)
{
	return x&(-x);
}
ll c[300300];
void add(int x,int v)
{
//	cout<<x<<' '<<v<<endl;
	for(int i=x;i<=n;i+=lowbit(i))
		c[i]+=v;
}
ll ask(int x)
{
	ll ret=0;
	for(int i=x;i>0;i-=lowbit(i))
		ret+=c[i];
	return ret;
}
int mdeep[300005],deep[300005],fa[300005];
void dfs(int now)
{
//	cout<<now<<' '<<fa<<endl; 
//	tr[hash[now]].v=v[now];
	mdeep[now]=deep[now];
	int l=0,r=0;
	for(int i=head[now];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa[now])continue;
	/*	if(l==0)l=hash[to];
		if(r==0)r=hash[to];
		if(hash[to]<l)l=hash[to];
		if(hash[to]>r)r=hash[to];
	*/
		deep[to]=deep[now]+1;	
		fa[to]=now;	
		dfs(to);
		mdeep[now]=max(mdeep[to],mdeep[now]);
	}
//	tr[hash[now]].l=l;tr[hash[now]].r=r;
	add(hash[now],v[now]);
//	cout<<now<<' '<<hash[now]<<' '<<tr[hash[now]].v<<' '<<tr[hash[now]].l<<' '<<tr[hash[now]].r<<endl;
}
int newdeep,newroot,bz;
int xiao,da;
void findx(int now,int sd)
{
//	cout<<now<<' '<<sd<<' '<<fa[now]<<endl;
	if(sd==newdeep)
	{
		if(xiao==0)
			xiao=hash[now];
		else xiao=min(xiao,hash[now]);
		if(da==0)da=hash[now];
		else da=max(da,hash[now]);
		return ;
	}
	int small=0,x=-1,y=-1,big=99999999;
	for(int i=head[now];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa[now])continue;
		if(mdeep[ to ]-deep[newroot]>=bz)
		{
			if(small==0)small=hash[to],x=to;
			else if(small>hash[to])
			{
				small=hash[to];x=to;
			}
			if(da==0)big=hash[to],y=to;
			else if(big<hash[to])
			{
				big=hash[to];y=to;
			}
		}
	}
	if(x!=-1)findx(x,sd+1);
	if(y!=-1)findx(y,sd+1);
}

int main()
{
//	freopen("abcd.in","r",stdin);
	freopen("newweapon.in","r",stdin);
	freopen("newweapon.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
		v[i]=read();
	for(int i=1;i<n;i++)
	{
		int x,y;x=read();y=read();
		insert(x,y);
		insert(y,x);
	}
	bfs();
//	cout<<hash[3]<<' ';
//	for(int i=1;i<=n;i++)
//		cout<<i<<' '<<hash[i]<<endl;
	dfs(1);
//	for(int i=1;i<=n;i++)
//		cout<<i<<' '<<c[i]<<endl;
	int sbt=read();
//	sbdeep=1;
//	cout<<yez(1,0);return 0;
	
	while(sbt--)
	{
		int x=read(),y=read(),z=read();
		if(x==2)
		{
			newdeep=z;
			newroot=y;
		//	cout<<x<<' '<<y<<' '<<z<<' '<<sb<<' '<<sd<<endl;
			bz=z;
			xiao=da=0;
			findx( y, 0);
			printf("%lld\n", ask(da)-ask(xiao-1)  );
		}
		else
		{
			add(hash[y],z-v[y]);
		}
	}
	return 0;
}