1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 60000+5 14 #define maxm 100000+5 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define for4(i,k,x) for(int i=head[k][x],y=e[k][i].go;i;i=e[k][i].next,y=e[k][i].go) 23 #define mod 1000000007 24 using namespace std; 25 inline int read() 26 { 27     int x=0,f=1;char ch=getchar(); 28     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30     return x*f; 31 } 32 struct rec 33 { 34     int a[1500],n; 35     inline void insert(int x) 36     { 37         int i=++n; 38         for(;i>1&&a[i-1]>x;i--)a[i]=a[i-1]; 39         a[i]=x; 40     } 41     inline void modify(int x,int y) 42     { 43         int i=lower_bound(a+1,a+n+1,x)-a; 44         for(;i<n&&a[i+1]<y;i++)a[i]=a[i+1]; 45         for(;i>1&&a[i-1]>y;i--)a[i]=a[i-1]; 46         a[i]=y; 47     } 48     inline int query(int x) 49     { 50         return n-(upper_bound(a+1,a+n+1,x)-a)+1; 51     } 52 }s[10000]; 53 int n,m,ans,size,cnt,top[maxn],tot[2],head[2][maxn],a[maxn],fa[maxn],b[maxn]; 54 struct edge{int go,next;}e[2][2*maxn]; 55 inline void add(int k,int x,int y) 56 { 57     e[k][++tot[k]]=(edge){y,head[k][x]};head[k][x]=tot[k]; 58 } 59 inline void dfs(int x) 60 { 61     for4(i,0,x)if(y!=fa[x]) 62     { 63         fa[y]=x; 64         if(s[b[x]].n<size)s[b[y]=b[x]].insert(a[y]); 65         else top[b[y]=++cnt]=y,s[cnt].insert(a[y]),add(1,b[x],b[y]); 66         dfs(y); 67     } 68 } 69 inline void query2(int x,int w) 70 { 71     ans+=s[x].query(w); 72     for4(i,1,x)query2(y,w); 73 } 74 inline void query1(int x,int w) 75 { 76     if(a[x]>w)ans++; 77     for4(i,0,x)if(y!=fa[x]){if(top[b[y]]==y)query2(b[y],w);else query1(y,w);} 78 } 79 int main() 80 { 81     freopen("input.txt","r",stdin); 82     freopen("output.txt","w",stdout); 83     n=read(); 84     for1(i,n-1){int x=read(),y=read();add(0,x,y);add(0,y,x);} 85     for1(i,n)a[i]=read(); 86     s[b[1]=top[1]=cnt=1].insert(a[1]); 87     size=sqrt(2*n*log2(n)); 88     dfs(1); 89     m=read(); 90     while(m--) 91     { 92         int op=read(),x=read()^ans,y=read()^ans; 93         if(op==0) 94         { 95             ans=0; 96             if(top[b[x]]!=x)query1(x,y); 97             else query2(b[x],y); 98             printf("%d\n",ans); 99         }else if(op==1)100         {101             s[b[x]].modify(a[x],y);102             a[x]=y;103         }else104         {105             a[++n]=y;add(0,x,n);fa[n]=x;106             if(s[b[x]].n<size)s[b[n]=b[x]].insert(a[n]);107             else top[b[n]=++cnt]=n,s[cnt].insert(a[n]),add(1,b[x],b[n]);108         }109     }110     return 0;111 }