记录编号	373741	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	3.741 s
提交时间	2017-02-21 18:30:46	内存使用	37.77 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
#define Lowbit(x) (x&-x)
#define ls(x) (a[x].lc)
#define rs(x) (a[x].rc)
const int maxn=35000;
const int Max=10000;
struct Node{
	int lc,rc,sum;
}a[maxn*100];
struct Edge{
	int next,to;
}e[maxn*2];
int len,head[maxn];
int root[maxn],n,cnt,v[maxn],id[maxn],Last[maxn],pos;
int ra[maxn],rb[maxn],s[maxn];
void Add_edge(int x,int y){
	len++;
	e[len].to=y;
	e[len].next=head[x];
	head[x]=len;
}
void Insert(int x,int add,int opt,int & rt,int l,int r){
	if(!rt || opt){
		a[++cnt]=a[rt];
		rt=cnt;
	}
	a[rt].sum+=add;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)Insert(x,add,opt,ls(rt),l,mid);
	else Insert(x,add,opt,rs(rt),mid+1,r);
}
void Bit_Update(int x,int p,int add){
	for(int i=x;i<=n;i+=Lowbit(i))Insert(p,add,0,s[i],1,Max);
}
void Dfs(int x,int fa){
	id[x]=++pos;
	root[pos]=root[pos-1];
	Insert(v[x],1,1,root[pos],1,Max);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(j!=fa)Dfs(j,x);
	}
	Last[x]=pos;
}
int Query(int k,int pr,int rt,int l,int r){
	if(l==r)return l;
	int res=a[ls(rt)].sum-a[ls(pr)].sum;
	for(int i=1;i<=ra[0];i++)res-=a[ls(ra[i])].sum;
	for(int i=1;i<=rb[0];i++)res+=a[ls(rb[i])].sum;
	int mid=(l+r)>>1;
	if(res>=k){
		for(int i=1;i<=ra[0];i++)ra[i]=ls(ra[i]);
		for(int i=1;i<=rb[0];i++)rb[i]=ls(rb[i]);
		return Query(k,ls(pr),ls(rt),l,mid);
	}
	else{
		for(int i=1;i<=ra[0];i++)ra[i]=rs(ra[i]);
		for(int i=1;i<=rb[0];i++)rb[i]=rs(rb[i]);
		return Query(k-res,rs(pr),rs(rt),mid+1,r);
	}
}
int Get_sum(int s,int t,int rt,int l,int r){
	if(s<=l && t>=r)return a[rt].sum;
	int mid=(l+r)>>1;
	if(t<=mid)return Get_sum(s,t,ls(rt),l,mid);
	if(s>mid)return Get_sum(s,t,rs(rt),mid+1,r);
	return Get_sum(s,t,ls(rt),l,mid)+Get_sum(s,t,rs(rt),mid+1,r);
}
int Sum(int s,int t,int pr,int rt){
	int tot=0;
	tot+=Get_sum(s,t,rt,1,Max);
	tot-=Get_sum(s,t,pr,1,Max);
	for(int i=1;i<=ra[0];i++)tot-=Get_sum(s,t,ra[i],1,Max);
	for(int i=1;i<=rb[0];i++)tot+=Get_sum(s,t,rb[i],1,Max);
	return tot;
}
void Copy(int l,int r){
	ra[0]=rb[0]=0;
	for(int i=l-1;i;i-=Lowbit(i))ra[++ra[0]]=s[i];
	for(int i=r  ;i;i-=Lowbit(i))rb[++rb[0]]=s[i];
}
void Init();
int main(){
	freopen("hjtree.in","r",stdin);freopen("hjtree.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&v[i]);
	for(int i=1;i<n;i++){
		int x,y;scanf("%d%d",&x,&y);
		Add_edge(x,y);Add_edge(y,x);
	}
	Dfs(1,0);
	int Q;scanf("%d",&Q);
	while(Q--){
		int type,u,x,y;scanf("%d",&type);
		int l,r;
		if(type==1){
			scanf("%d%d",&u,&x);
			l=id[u],r=Last[u];
			// printf("<<%d %d>>",l,r);
			Copy(l,r);
			printf("%d\n",Query(x,root[l-1],root[r],1,Max));
		}
		else if(type==2){
			scanf("%d%d%d",&u,&x,&y);
			l=id[u],r=Last[u];
			Copy(l,r);
			printf("%d\n",Sum(x,y,root[l-1],root[r]));	
		}
		else if(type==3){
			scanf("%d%d",&u,&x);
			Bit_Update(id[u],v[u],-1);
			v[u]=x;
			Bit_Update(id[u],v[u],1);
			
		}
	}
}

/*

5
3 4 6 1 2
1 2
1 3
3 4
3 5
7
1 1 4
2 1 1 5
3 4 5
1 1 4
2 3 3 6
3 5 7
1 3 3
 */