一代神题啊orz（至少是以前年代的神题吧）
块状树
复杂度nsqrtnlogn
真是exciting
还没有卡时限
话不多说直接上代码
（最近解锁了记事本写代码的技能...感觉越来越依赖OJ调试了...啊感觉写代码准确率高了不少qwq）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define N 200006
#define M 400006 using namespace std;
inline int read(){
int ret=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while ('0'<=ch&&ch<='9'){
ret=ret*10-48+ch;
ch=getchar();
}
return ret;
} const int KK=400;
vector<int> seq[N]; struct edge{
int adj,next;
edge(){}
edge(int _adj,int _next):adj(_adj),next(_next){}
} e[M];
int n,g[N],m;
void AddEdge(int u,int v){
e[++m]=edge(v,g[u]);g[u]=m;
e[++m]=edge(u,g[v]);g[v]=m;
}
int w[N]; vector<int> nxt[N];
int fa[N],bl[N],sz[N],cnt,top[N];
void refresh(int u,int p){
for (;p>0&&seq[u][p]<seq[u][p-1];--p)swap(seq[u][p],seq[u][p-1]);
for (;p<sz[u]-1&&seq[u][p]>seq[u][p+1];++p)swap(seq[u][p],seq[u][p+1]);
}
void newnode(int u){
if (sz[bl[fa[u]]]==KK){
sz[bl[u]=++cnt]=0;
top[cnt]=u;
}
else bl[u]=bl[fa[u]];
++sz[bl[u]];
}
void dfs(int u){
newnode(u);
for (int i=g[u];i;i=e[i].next){
int v=e[i].adj;
if (v==fa[u]) continue;
fa[v]=u;
dfs(v);
}
}
void dfs_pre(int u){
seq[bl[u]].push_back(w[u]);++sz[bl[u]];
for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u){
int v=e[i].adj;
if (bl[v]==bl[u]) dfs_pre(v);
else nxt[bl[u]].push_back(bl[v]);
}
}
void prepare(int id){
seq[id].clear();vector<int>(seq[id]).swap(seq[id]);
nxt[id].clear();vector<int>(nxt[id]).swap(nxt[id]);
sz[id]=0;
dfs_pre(top[id]);
sort(seq[id].begin(),seq[id].end());
} int solve(int u,int lmt){
int l=-1,r=sz[u],mid;
while (l+1<r){
mid=l+r>>1;
if (seq[u][mid]<=lmt) l=mid;
else r=mid;
}
int ret=sz[u]-l-1;
for (int j=nxt[u].size()-1;j>=0;--j) ret+=solve(nxt[u][j],lmt);
return ret;
}
int query(int u,int lmt){
if (bl[u]!=bl[fa[u]]) return solve(bl[u],lmt);
int ret=w[u]>lmt;
for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u)ret+=query(e[i].adj,lmt);
return ret;
} void modify(int u,int x){
int p;
for (int i=0;i<sz[bl[u]];++i)
if (seq[bl[u]][i]==w[u]){p=i;break;}
w[u]=x;seq[bl[u]][p]=x;
refresh(bl[u],p);
} void create(int u,int x){
AddEdge(u,++n);fa[n]=u;w[n]=x;
int tmp=cnt;
newnode(n);
seq[bl[n]].push_back(w[n]);
refresh(bl[n],sz[bl[n]]-1);
if (tmp<cnt) nxt[bl[u]].push_back(cnt);
} void dfs_update(int u,int last,int now){
bl[u]=now;
for (int i=g[u];i;i=e[i].next)if (fa[e[i].adj]==u)
if (bl[e[i].adj]==last) dfs_update(e[i].adj,last,now);
} void cut(int u){
int lst=bl[u];
if (bl[fa[u]]!=bl[u]){
int f=bl[fa[u]];
for (vector<int>::iterator it=nxt[f].begin();it!=nxt[f].end();++it)
if ((*it)==lst){nxt[f].erase(it);break;}
fa[u]=0;return;
}
top[++cnt]=u;
fa[u]=0;
dfs_update(u,lst,cnt);
prepare(lst);
prepare(cnt);
} int main(){
n=read();
memset(g,0,sizeof(g));m=1;
for (int i=1;i<n;++i) AddEdge(read(),read());
for (int i=1;i<=n;++i) w[i]=read();
fa[1]=0;bl[0]=0;sz[0]=KK;cnt=0;
dfs(1);
int lastans=0;
for (int i=1;i<=cnt;++i) prepare(i);
for (int Q=read();Q;Q--){
int op=read(),u=read()^lastans,x;
if (op<3) x=read()^lastans;
else cut(u);
if (op==0) printf("%d\n",lastans=query(u,x));
else if (op==1) modify(u,x);
else if (op==2) create(u,x);
}
return 0;
}