rt，如题，按照第三篇题解的思路对时间分块，打了归并树，然后全部 MLE，有没有大佬帮帮忙看看？码风有点丑请见谅。/ll

#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N=6e4+10,K=log2(N)+2;
int n,m,k,B,a[N],bg[N],ed[N],id[N],f[N][K],dep[N],lg[N];vector<int>e[N];struct opts{int op,x,y,z;};vector<opts>tmp;
vector<int>t[N<<2];vector<int>::iterator i,j;
void build(int l=1,int r=id[0],int rt=1){
	t[rt].clear();if(l==r)return t[rt].push_back(a[id[l]]);int mid=(l+r)>>1;
	build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);i=t[rt<<1].begin(),j=t[rt<<1|1].begin();
	while(i!=t[rt<<1].end()&&j!=t[rt<<1|1].end())t[rt].push_back(*((*i<*j?i:j)++));
	while(i!=t[rt<<1].end())t[rt].push_back(*(i++));while(j!=t[rt<<1|1].end())t[rt].push_back(*(j++));
}
int get(int L,int R,int x,int l=1,int r=id[0],int rt=1){
	if(L<=l&&r<=R)return t[rt].end()-upper_bound(t[rt].begin(),t[rt].end(),x);int mid=(l+r)>>1,s=0;
	if(L<=mid)s+=get(L,R,x,l,mid,rt<<1);if(mid<R)s+=get(L,R,x,mid+1,r,rt<<1|1);return s;
}
void dfs(int u){id[bg[u]=++id[0]]=u;for(int v:e[u])if(v^f[u][0])dep[v]=dep[u]+1,f[v][0]=u,dfs(v);ed[u]=id[0];}
void reset(){tmp.clear();id[0]=0;dfs(dep[1]=1);build();}
bool isin(int x,int y){while(dep[x]>dep[y])x=f[x][lg[dep[x]-dep[y]]];return x==y;}
int main(){
	freopen("1.in","r",stdin);
	scanf("%d",&n);for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=2;i<N;i++)lg[i]=lg[i>>1]+1;reset();scanf("%d",&m);k=log2(n+m);
	B=sqrt(m);for(int i=1;i<=k;i++)for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];for(int op,u,x,ans=0;m--;){
		scanf("%d%d%d",&op,&u,&x);u^=ans,x^=ans;if(!op){
			ans=get(bg[u],ed[u],x);for(opts o:tmp){
				if(o.op==1){if((o.y>x)^(o.z>x)&&isin(o.x,u))ans+=o.y>x?-1:1;}else if(o.z>x&&isin(o.x,u))ans++;
			}printf("%d\n",ans);
		}else{
			if(op==2){tmp.push_back({op,++n,u,x});f[n][0]=u;a[n]=x;dep[n]=dep[u]+1;
				for(int i=1;i<=k;i++)f[n][i]=f[f[n][i-1]][i-1];e[n].push_back(u);e[u].push_back(n);}
			else tmp.push_back({op,u,a[u],x}),a[u]=x;(int)tmp.size()>=B&&(reset(),0);
		}
	}
	return 0;
}

``