记录编号	548742	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	15.913 s
提交时间	2020-01-30 18:30:32	内存使用	106.60 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#define R register
#define LL inline
using namespace std;
struct PE
{
	int v,ff,ch[2],size,cnt;
};
PE t[4800005];
int root[120005],fa[30005],V[30005];
vector<int> b[30005];
int n,q,tot;
int INF=2147483647;
int read()
{
	int x=0,ju=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
	    if(c=='-')
		{
		    ju=-1;
		}
		c=getchar();
	}
	while(c<='9'&&c>='0')
	{
	    x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*ju;
}
LL void pushup(int x)
{
	t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
LL void rotate(int x)
{
	int y=t[x].ff;
	int z=t[y].ff;
	int k=(t[y].ch[1]==x);
	t[z].ch[t[z].ch[1]==y]=x;
	t[y].ch[k]=t[x].ch[k^1];
	t[t[x].ch[k^1]].ff=y;
	t[x].ch[k^1]=y;
	t[y].ff=x;
	t[x].ff=z;
	pushup(y);
	pushup(x);
}
LL void Splay(int x,int goal,int &root)
{
	while(t[x].ff!=goal)
	{
		int y=t[x].ff;
		int z=t[y].ff;
		if(z!=goal)
		{
			(t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);
		}
		rotate(x);
	}
	if(goal==0)
		root=x;
}
LL void Insert(int x,int &root)
{
	int u=root,ff;
	while(u&&t[u].v!=x)
	{
		ff=u;
		u=t[u].ch[t[u].v<x];
	}
	if(t[u].v==x)
		t[u].cnt++;
	else
	{
		u=++tot;
		t[u].v=x;
		t[u].ff=ff;
		if(ff)
			t[ff].ch[x>t[ff].v]=u;
		t[u].cnt=1;
		t[u].size=1;
		t[u].ch[0]=t[u].ch[1]=0;
	}
	Splay(u,0,root);
}
LL void Find(int x,int &root)
{
	int u=root;
	while(t[u].ch[x>t[u].v]&&t[u].v!=x)
	{
		u=t[u].ch[x>t[u].v];
	}
	Splay(u,0,root);
}
LL int Rank(int x,int &root)
{
	Find(x,root);
	if(x<=t[root].v)
	return t[t[root].ch[0]].size+1;
	if(x>t[root].v)
		return t[t[root].ch[0]].size+t[root].cnt+1;
}
LL int KTH(int x,int &root)
{
	int u=root;
	if(t[u].size<x)
		return -2147483647;
	while(1)
	{
		int y=t[u].ch[0];
		if(t[y].size+t[u].cnt<x)
		{
			x-=t[y].size+t[u].cnt;
			u=t[u].ch[1];
		}
		else
		{
			if(t[y].size>=x)
				u=t[u].ch[0];
			else
				return t[u].v;
		}
	}
}
LL int Next(int x,int f,int &root)
{
	Find(x,root);
	int u=root;
	if(t[u].v>x&&f)
		return u;
	if(t[u].v<x&&!f)
		return u;
	u=t[u].ch[f];
	while(t[u].ch[f^1])
		u=t[u].ch[f^1];
	return u;
}
LL void Delete(int x,int &root)
{
	int last=Next(x,0,root);
	int ext=Next(x,1,root);
	Splay(last,0,root);
	Splay(ext,last,root);
	int del=t[ext].ch[0];
	if(t[del].cnt>1)
	{
		t[del].cnt--;
		Splay(del,0,root);
	}
	else
		t[ext].ch[0]=0;
}
LL void DFS(int x,int f)
{
	root[x]=++tot;
	Insert(INF,root[x]);
	Insert(-INF,root[x]);
	fa[x]=f;
	for(int i=0;i<b[x].size();i++)
	{
		int to=b[x][i];
		if(to==f)
			continue;
		DFS(to,x);
	}
}
LL void ADD()
{
	for(R int i=1;i<=n;i++)
	{
		R int u=i;
		while(1)
		{
			if(u==1)
			{
				Insert(V[i],root[u]);
				break;
			}
			else
			{
				Insert(V[i],root[u]);
				u=fa[u];
			}
		}
	}
}
LL int Check(int u,int k)
{
	return KTH(k,root[u]);
}
LL int Query(int u,int a,int b)
{
	return Rank(b+1,root[u])-Rank(a,root[u]);
}
LL void Change(int u,int x)
{
	R int ts=u;
	while(1)
	{
		Delete(V[u],root[ts]);
		Insert(x,root[ts]);
		if(ts==1)
			break;
		else
			ts=fa[ts];
	}
	V[u]=x;
}
int LINYIN()
{
	freopen("hjtree.in","r",stdin);
	freopen("hjtree.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
	{
		V[i]=read();
		//scanf("%d",&V[i]);
	}
	int a1,a2,a3,a4;
	for(int i=1;i<n;i++)
	{
		a1=read();
		a2=read(); 
		b[a1].push_back(a2);
		b[a2].push_back(a1);
	}
	DFS(1,0);
	ADD();
	q=read();
	//scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		a1=read();
		a2=read();
		a3=read();
		//scanf("%d%d%d",&a1,&a2,&a3);
		if(a1==1)
		{
			printf("%d\n",Check(a2,a3+1));
		}
		if(a1==2)
		{
			a4=read();
			//scanf("%d",&a4);
			printf("%d\n",Query(a2,a3,a4));
		}
		if(a1==3)
		{
			Change(a2,a3);
		}
	}
	return 0;
}
int sed=LINYIN();
int main()
{
	;
}