记录编号	463562	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	2.073 s
提交时间	2017-10-24 13:37:37	内存使用	115.44 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[30005];
inline void insert(int s,int e){edge *tmp(new edge);tmp->e=e;tmp->n=pre[s];pre[s]=tmp;}
int n,q,cnt,timee;
int w[30005],l[30005],r[30005],pos[30005];
inline void dfs(int u,int fa){
	l[u]=++timee;pos[timee]=u;
	for(edge *i=pre[u];i;i=i->n)if(i->e!=fa)dfs(i->e,u);
	r[u]=timee;
}
int root[30005],lch[10000005],rch[10000005],sum[10000005],a,b,L[30],R[30],size(10000);
inline int lowbit(int x){return x&-x;}
inline void update(int &x,int las,int pos,int w,int l,int r){
	x=++cnt;lch[x]=lch[las];rch[x]=rch[las];sum[x]=sum[las]+w;
	if(l==r)return;int mid((l+r)>>1);
	if(pos<=mid)update(lch[x],lch[las],pos,w,l,mid);
	else update(rch[x],rch[las],pos,w,mid+1,r);
}
inline int query(int l,int r,int k){
	if(l==r)return l;
	int mid((l+r)>>1),suml(0),sumr(0);
	for(int i=1;i<=a;++i)suml+=sum[lch[L[i]]];
	for(int i=1;i<=b;++i)sumr+=sum[lch[R[i]]];
	if(k<=sumr-suml){
		for(int i=1;i<=a;++i)L[i]=lch[L[i]];
		for(int i=1;i<=b;++i)R[i]=lch[R[i]];
		return query(l,mid,k);
	}
	else{
		for(int i=1;i<=a;++i)L[i]=rch[L[i]];
		for(int i=1;i<=b;++i)R[i]=rch[R[i]];
		return query(mid+1,r,k-(sumr-suml));
	}
}
inline int query_sum(int ll,int rr,int l,int r){
	if(ll<=l&&r<=rr){
		int ret(0);
		for(int i=1;i<=b;++i)ret+=sum[R[i]];
		for(int i=1;i<=a;++i)ret-=sum[L[i]];
		return ret;
	}
	int tmpl[30],tmpr[30];
	int mid((l+r)>>1),ret(0);
	for(int i=1;i<=a;++i)tmpl[i]=L[i];
	for(int i=1;i<=b;++i)tmpr[i]=R[i];
	if(ll<=mid){
		for(int i=1;i<=a;++i)L[i]=lch[L[i]];
		for(int i=1;i<=b;++i)R[i]=lch[R[i]];
		ret+=query_sum(ll,rr,l,mid);
	}
	if(mid<rr){
		for(int i=1;i<=a;++i)L[i]=rch[tmpl[i]];
		for(int i=1;i<=b;++i)R[i]=rch[tmpr[i]];
		ret+=query_sum(ll,rr,mid+1,r);
	}
	for(int i=1;i<=a;++i)L[i]=tmpl[i];
	for(int i=1;i<=b;++i)R[i]=tmpr[i];
	return ret;
}
int main(){
	freopen("hjtree.in","r",stdin);
	freopen("hjtree.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)
		for(int j=i;j<=n;j+=lowbit(j))
			update(root[j],root[j],w[pos[i]],1,1,size);
	q=read();
	while(q--){
		int op(read());
		if(op==1){
			int x(read()),y(read());
			a=b=0;
			for(int i=l[x]-1;i;i-=lowbit(i))L[++a]=root[i];
			for(int i=r[x];i;i-=lowbit(i))R[++b]=root[i];
			printf("%d\n",query(1,size,y));
		}
		if(op==2){
			int x(read()),y(read()),z(read());a=b=0;
			for(int i=l[x]-1;i;i-=lowbit(i))L[++a]=root[i];
			for(int i=r[x];i;i-=lowbit(i))R[++b]=root[i];
			printf("%d\n",query_sum(y,z,1,size));
		}
		if(op==3){
			int x(read()),y(read());
			for(int i=l[x];i<=n;i+=lowbit(i))update(root[i],root[i],w[x],-1,1,size);
			w[x]=y;
			for(int i=l[x];i<=n;i+=lowbit(i))update(root[i],root[i],y,1,1,size);
		}
	}
}