询问的化我们可以建主席树。然后修改？，树套树。。。，最后插入？炸了。
所以我们对操作进行分块。
我们先对整棵树建一个主席树。修改，插入我们先记录下来。然后询问的时候先对主席树查询，然后暴力遍历我们记录下来的修改插入操作。每(sqrt{m})次操作后我们重新构建一个主席树。这样我们保证了重建主席树和询问的总复杂度为(O(nlognsqrt{m}))然后就把这道题解决了。
有一个难办的事就是如何记录修改和插入的操作。可以使每次询问的时候我们可以知道修改和插入是否在(u)的子树中以便我们判断是否要让这些修改和询问产生贡献。因为没考虑到可以询问插入的节点，在多次尝试后我决定维护一个(f[i][j])代表i向上跳(i^j)的深度到达的节点。处理询问的时候我们对于每一个修改和插入都跳到和u一个深度看是否相等。
当然还要记录一些常规的信息比如这个点被修改之前的权值什么的。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=101000;
int head[N],cnt;
int n,m,ans,a[N],b[N],CNT,more;
int be[N],ed[N],dep[N],fa[N][25],tot,id[N],top,w[N],from[N];
int root[N],ch[N*20][2],sum[N*20],num;
struct edge{
int to,nxt;
}e[N*2];
inline void add_edge(int u,int v){
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
inline void add(int l,int r,int x,int pre,int &now){
now=++num;
sum[now]=sum[pre]+1;
ch[now][0]=ch[pre][0];
ch[now][1]=ch[pre][1];
if(l==r)return;
int mid=(l+r)>>1;
if(x>mid)add(mid+1,r,x,ch[pre][1],ch[now][1]);
else add(l,mid,x,ch[pre][0],ch[now][0]);
}
inline int check(int l,int r,int L,int R,int pre,int now){
if(l==L&&r==R)return sum[now]-sum[pre];
int mid=(l+r)>>1;
if(L>mid)return check(mid+1,r,L,R,ch[pre][1],ch[now][1]);
else if(R<=mid)return check(l,mid,L,R,ch[pre][0],ch[now][0]);
else return check(l,mid,L,mid,ch[pre][0],ch[now][0])+check(mid+1,r,mid+1,R,ch[pre][1],ch[now][1]);
}
inline void dfs(int u,int f){
be[u]=++tot;
dep[u]=dep[f]+1;
add(1,n,lower_bound(b+1,b+1+n,a[u])-b,root[be[u]-1],root[be[u]]);
fa[u][0]=f;
for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f)continue;
dfs(v,u);
}
ed[u]=tot;
}
inline bool judge(int x,int to){
for(int i=20;i>=0;i--)
if(dep[fa[x][i]]>=dep[to])x=fa[x][i];
if(x==to)return true;
else return false;
}
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}
return sum*f;
}
int main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add_edge(u,v);add_edge(v,u);
}
for(int i=1;i<=n;++i)a[i]=read();
m=read();
int Block=sqrt(m*25);
while(m--){
int type=read(),u=read()^ans,x=read()^ans;
if(CNT==0){
tot=0;top=0;num=0;n+=more;more=0;
for(int i=1;i<=n;i++)b[i]=a[i];
sort(b+1,b+1+n);
dfs(1,1);
}
if(type==0){
if(u<=n){
int tmp=upper_bound(b+1,b+1+n,x)-b;
if(tmp<=n)ans=check(1,n,tmp,n,root[be[u]-1],root[ed[u]]);
else ans=0;
}
else ans=0;
for(int i=1;i<=top;++i)
if(judge(id[i],u)){
if(from[i]>x)ans--;
if(w[i]>x)ans++;
}
for(int i=n+1;i<=n+more;++i){
if(judge(i,u)){
if(w[i]>x)ans++;
}
}
printf("%d
",ans);
CNT++;
}
else if(type==1){
++top;
w[top]=x;from[top]=a[u];id[top]=u;
++CNT;
a[u]=x;
}
else{
++more;
add_edge(n+more,u);
add_edge(u,n+more);
a[n+more]=x;
fa[n+more][0]=u;dep[n+more]=dep[u]+1;
for(int i=1;i<=20;i++)fa[n+more][i]=fa[fa[n+more][i-1]][i-1];
w[n+more]=x;
++CNT;
}
if(CNT==Block)CNT=0;
}
return 0;
}