我曾在弦歌之中听过你，
檀板声碎，半出折子戏。
舞榭歌台被风吹去，
岁月深处尚有余音一缕……

Gty神(xian)犇(chong)从来不缺妹子……
他来到了一棵妹子树下，发现每个妹子有一个美丽度……
由于Gty很哲♂学，他只对美丽度大于某个值的妹子感兴趣。
他想知道某个子树中美丽度大于k的妹子个数。
某个妹子的美丽度可能发生变化……
树上可能会出现一只新的妹子……

维护一棵初始有n个节点的有根树(根节点为1)，树上节点编号为1-n，每个点有一个权值wi。
支持以下操作：
0 u x          询问以u为根的子树中，严格大于x的值的个数。(u^=lastans,x^=lastans)
1 u x          把u节点的权值改成x。(u^=lastans,x^=lastans)
2 u x          添加一个编号为"当前树中节点数+1"的节点，其父节点为u，其权值为x。(u^=lastans,x^=lastans)
最开始时lastans=0。

输入第一行包括一个正整数n(1<=n<=30000)，代表树上的初始节点数。
接下来n-1行，每行2个整数u,v，为树上的一条无向边。
任何时刻，树上的任何权值大于等于0，且两两不同。
接下来1行，包括n个整数wi，表示初始时每个节点的权值。
接下来1行，包括1个整数m(1<=m<=30000)，表示操作总数。
接下来m行，每行包括三个整数 op,u,v：
op,u,v的含义见题目描述。
保证题目涉及的所有数在int内。

对每个op=0，输出一行，包括一个整数，意义见题目描述。

  1 //It is made by wfj_2048~  2 #include <algorithm>  3 #include <iostream>  4 #include <cstring>  5 #include <cstdlib>  6 #include <cstdio>  7 #include <vector>  8 #include <cmath>  9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define inf (1<<30) 14 #define N (500010) 15 #define il inline 16 #define RG register 17 #define ll long long 18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 19  20 using namespace std; 21  22 struct edge{ int nt,to; }G[N],g[N]; 23  24 int Head[N],head[N],sz[N],st[N],top[N],fa[N],bl[N],a[N],w[N],T,n,m,num,Num,ans,cnt,block; 25  26 vector <int> val[N]; 27  28 il int gi(){ 29     RG int x=0,q=1; RG char ch=getchar(); 30     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 31     if (ch==‘-‘) q=-1,ch=getchar(); 32     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 33     return q*x; 34 } 35  36 il void insert(RG int from,RG int to){ 37     g[++num]=(edge){head[from],to},head[from]=num; return; 38 } 39  40 il void link(RG int from,RG int to){ 41     G[++Num]=(edge){Head[from],to},Head[from]=Num; return; 42 } 43  44 il void dfs1(RG int x,RG int p){ 45     RG int tp=T; fa[x]=p,st[++T]=x; 46     for (RG int i=head[x];i;i=g[i].nt) if (g[i].to!=p) dfs1(g[i].to,x); 47     if (T-tp>=block){ 48     ++cnt; while (T>tp) a[++sz[cnt]]=w[st[T]],bl[st[T--]]=cnt; 49     sort(a+1,a+sz[cnt]+1); for (RG int j=1;j<=sz[cnt];++j) val[cnt].push_back(a[j]); 50     } 51     return; 52 } 53  54 il void dfs2(RG int x,RG int p){ 55     for (RG int i=head[x],v;i;i=g[i].nt){ 56     v=g[i].to; if (v==p) continue; dfs2(v,x); 57     if (bl[x]!=bl[v]) top[bl[v]]=v,link(bl[x],bl[v]); 58     } 59     return; 60 } 61  62 il int find(RG int x,RG int k){ 63     RG int ans=0,l=0,r=sz[x]-1,mid; 64     while (l<=r){ 65     mid=(l+r)>>1; 66     if (val[x][mid]<=k) ans=mid+1,l=mid+1; 67     else r=mid-1; 68     } 69     return sz[x]-ans; 70 } 71  72 il int calc1(RG int x,RG int k){ 73     RG int res=find(x,k); 74     for (RG int i=Head[x];i;i=G[i].nt) res+=calc1(G[i].to,k); 75     return res; 76 } 77  78 il int calc2(RG int x,RG int p,RG int k){ 79     RG int res=w[x]>k,v; 80     for (RG int i=head[x];i;i=g[i].nt){ 81     v=g[i].to; if (v==p) continue; 82     if (bl[x]==bl[v]) res+=calc2(v,x,k); 83     else res+=calc1(bl[v],k); 84     } 85     return res; 86 } 87  88 il int query(RG int x,RG int k){ 89     RG int ans=0; 90     if (top[bl[x]]==x) ans=calc1(bl[x],k); else ans=calc2(x,fa[x],k); 91     return ans; 92 } 93  94 il void work(){ 95     n=gi(); for (RG int i=1,u,v;i<n;++i) u=gi(),v=gi(),insert(u,v),insert(v,u); 96     for (RG int i=1;i<=n;++i) w[i]=gi(); block=245,dfs1(1,0); 97     if (T){ 98     top[++cnt]=1; while (T) a[++sz[cnt]]=w[st[T]],bl[st[T--]]=cnt; 99     sort(a+1,a+sz[cnt]+1); for (RG int i=1;i<=sz[cnt];++i) val[cnt].push_back(a[i]);100     }101     dfs2(1,0),m=gi();102     while (m--){103     RG int opt=gi(),x=gi()^ans,k=gi()^ans;104     if (!opt) ans=query(x,k),printf("%d\n",ans);105     if (opt==1){106         RG int B=bl[x],ccnt=0;107         for (RG int i=0;i<sz[B];++i)108         if (val[B][i]!=w[x]) a[++ccnt]=val[B][i];109         a[++ccnt]=w[x]=k,val[B].clear(),sort(a+1,a+ccnt+1);110         for (RG int i=1;i<=ccnt;++i) val[B].push_back(a[i]);111     }112     if (opt==2){113         insert(x,++n),fa[n]=x,w[n]=k;114         if (sz[bl[x]]>=block){115         top[++cnt]=n,sz[cnt]=1,link(bl[x],cnt);116         bl[n]=cnt,val[cnt].push_back(k);117         } else{118         RG int B=bl[x],ccnt=0; bl[n]=B,a[++ccnt]=w[n];119         for (RG int i=0;i<sz[B];++i) a[++ccnt]=val[B][i];120         val[B].clear(),sort(a+1,a+(++sz[B])+1);121         for (RG int i=1;i<=sz[B];++i) val[B].push_back(a[i]);122         }123     }124     }125     return;126 }127 128 int main(){129     File("gty");130     work();131     return 0;132 }