1 #include<cstdio>  2 #include<algorithm>  3 #include<cmath>  4 #include<vector>  5 using namespace std;  6 #define maxn 200001  7 int Res,Num;char C,CH[20];  8 inline int Ge()  9 { 10     Res=0;C=‘*‘;  11     while(C<‘0‘||C>‘9‘)C=getchar(); 12     while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();} 13     return Res; 14 } 15 inline void P(int x) 16 { 17     Num=0;if(!x){putchar(‘0‘);puts("");return;} 18     while(x>0)CH[++Num]=x%10,x/=10; 19     while(Num)putchar(CH[Num--]+48); 20     putchar(‘\n‘); 21 } 22 typedef vector<int>::iterator ITER; 23 vector<int>List[maxn],Goto[maxn]; 24 struct Graph 25 { 26     int v[maxn<<1],first[maxn<<1],next[maxn<<1],en; 27     void AddEdge(const int &a,const int &b) 28     {v[++en]=b;next[en]=first[a];first[a]=en;} 29 }; 30 Graph G,son; 31 int top[maxn],siz[maxn],sz,w[maxn],belong_tree[maxn]; 32 bool vis[maxn],root[maxn]; 33 int n,x,y,m,op,tree_num; 34 int ans,val,U; 35 void makeblock(int cur) 36 { 37     vis[cur]=true; 38     for(int i=G.first[cur];i;i=G.next[i]) 39       if(!vis[G.v[i]]) 40         { 41           son.AddEdge(cur,G.v[i]); 42           if(siz[top[cur]]<sz) 43             { 44               List[top[cur]].push_back(w[G.v[i]]); 45               siz[top[cur]]++; 46               top[G.v[i]]=top[cur]; 47             } 48           makeblock(G.v[i]); 49         } 50 } 51 void makeGoto(int cur) 52 { 53     for(int i=son.first[cur];i;i=son.next[i]) 54       { 55           if(top[son.v[i]]!=top[cur]) 56           Goto[top[cur]].push_back(son.v[i]); 57         makeGoto(son.v[i]); 58       } 59 } 60 void dfs(int cur)//在Goto树上询问  61 { 62     ans+=( List[cur].end() - upper_bound( List[cur].begin() , List[cur].end() , val ) ); 63     for(ITER it=Goto[cur].begin();it!=Goto[cur].end();it++) 64       if(belong_tree[*it]==belong_tree[cur])//通过标记控制在一棵树内  65         dfs(*it); 66 } 67 void dfs_block(int cur)//在块内询问  68 { 69     if(w[cur]>val) ans++; 70     for(int i=son.first[cur];i;i=son.next[i]) 71       if(top[son.v[i]]==top[cur]) dfs_block(son.v[i]); 72       else if(belong_tree[son.v[i]]==belong_tree[top[cur]]) dfs(son.v[i]); 73 } 74 void query() 75 { 76     ans=0; 77     if(U==top[U]) dfs(U); 78     else dfs_block(U); 79     P(ans); 80 } 81 void update() 82 { 83     List[top[U]].erase( lower_bound(List[top[U]].begin(),List[top[U]].end(),w[U]) ); 84     w[U]=val; 85     List[top[U]].insert( lower_bound(List[top[U]].begin(),List[top[U]].end(),val+1) , val ); 86 } 87 void AddPoint() 88 { 89     n++; 90     if(siz[top[U]]<sz) 91       { 92           top[n]=top[U]; 93           siz[top[n]]++; 94       } 95     else 96       { 97           top[n]=n; 98           siz[n]++; 99           Goto[top[U]].push_back(n);100           belong_tree[n]=belong_tree[top[U]];101       }102     son.AddEdge(U,n);103     w[n]=val;104     List[top[n]].insert( lower_bound(List[top[n]].begin(),List[top[n]].end(),val+1) , val );105 }106 void dfs_split(int cur)//设置每个块顶属于哪个树的标记 107 {108     for(ITER it=Goto[cur].begin();it!=Goto[cur].end();it++)109       if(belong_tree[cur]==belong_tree[*it])110         dfs_split(*it);111     belong_tree[cur]=tree_num;112 }113 void dfs_split_block(int cur)//把分裂的块的下半部分重构块 114 {115     List[U].push_back(w[cur]);116     for(int i=son.first[cur];i;i=son.next[i])117       {118           if(top[son.v[i]]==top[cur])119           dfs_split_block(son.v[i]);120         else if(belong_tree[son.v[i]]==belong_tree[top[U]])//顺手设置它下面的块的标记 121           {122             Goto[U].push_back(son.v[i]);123             dfs_split(son.v[i]);124           }125         siz[U]++;126       }127     top[cur]=U;128 }129 void dfs_remain_block(int cur)//把分裂的块的上半部分重构块 130 {131     List[top[U]].push_back(w[cur]); siz[top[U]]++;132     for(int i=son.first[cur];i;i=son.next[i])133       if( (!root[son.v[i]]) && (top[son.v[i]]==top[cur]) )134         dfs_remain_block(son.v[i]);135 }136 void Delete_Edge()137 {138     root[U]=true;139     tree_num++;140     if(U!=top[U])141       {142           List[top[U]].clear();siz[top[U]]=0;143           dfs_remain_block(top[U]);144           sort(List[top[U]].begin(),List[top[U]].end());//重构分裂的块的上半部分145           dfs_split_block(U);146           belong_tree[U]=tree_num;147           sort(List[U].begin(),List[U].end());//重构分裂的块的下半部分 148       }149     else150       dfs_split(U);151 }152 int main()153 {154     n=Ge();155     for(int i=1;i<n;i++)156       {157           x=Ge();y=Ge();158           G.AddEdge(x,y);159           G.AddEdge(y,x);160       }161     sz=sqrt((double)n*log2(n));162     for(int i=1;i<=n;i++)163       {164           w[i]=Ge();165           top[i]=i;166           siz[i]=1;167       }168     makeblock(1);169     for(int i=1;i<=n;i++)170       if(top[i]==i)171         {172           List[i].push_back(w[i]);173           sort(List[i].begin(),List[i].end());174         }175     makeGoto(1);176     root[1]=true;177     m=Ge();178     for(int i=1;i<=m;i++)179       {180           op=Ge();U=Ge();U^=ans;181           if(!op){val=Ge();val^=ans;query();}182           else if(op==1){val=Ge();val^=ans;update();}183           else if(op==2){val=Ge();val^=ans;AddPoint();}184           else Delete_Edge();185       }186     return 0;187 }