XXII.SP16580 QTREE7 - Query on a tree VII
它来了，它来了！LCT树套树的经典题，它来了！
虽然只是LCT套 std::multiset 而已
这题具体过程同QTREE6，不再赘述。唯一有区别的是，这题需要维护的是虚子树中最大值，不具有可减性。
因此，我们采用的方式就是用std::multiset维护所有虚儿子的值（两个实儿子单独考虑）。
因为此题的特殊性，在\(link\)时，可以直接连实边。因为当\(x\)在原树中的父亲被\(access+splay\)后，一定是它所在的LCT中深度最大的（两个实儿子在\(access\)中全扔掉了），因此可以直接把原树父亲的右儿子赋成\(x\)。
即：
inline void link(int x){splay(x),makeroot(pa[x]),fa[x]=pa[x],ch[1][pa[x]]=x,pushup(pa[x]);}
自然，我们这题还是可以写无根LCT，因此这里的\(makeroot\)仅仅是\(access+splay\)的简写（偷个懒）。
别忘了初值记得赋成\(-\infty\)，因为点权可以为负！
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,pa[100100],head[100100],cnt,col[100100];
struct Link_Cut_Tree{
#define lson ch[0][x]
#define rson ch[1][x]
int fa[100100],ch[2][100100],mx[100100],val[100100];
multiset<int>s[100100];//this s is for those imaginal subnodes
inline int identify(int x){
if(x==ch[0][fa[x]])return 0;
if(x==ch[1][fa[x]])return 1;
return -1;
}
inline void pushup(int x){
mx[x]=val[x];
if(lson)mx[x]=max(mx[x],mx[lson]);
if(rson)mx[x]=max(mx[x],mx[rson]);
if(!s[x].empty())mx[x]=max(mx[x],*s[x].rbegin());
}
inline void rotate(int x){
register int y=fa[x],z=fa[y],dirx=identify(x),diry=identify(y),b=ch[!dirx][x];
if(diry!=-1)ch[diry][z]=x;fa[x]=z;
if(b)fa[b]=y;ch[dirx][y]=b;
fa[y]=x,ch[!dirx][x]=y;
pushup(y),pushup(x);
}
inline void splay(int x){for(;identify(x)!=-1;rotate(x))if(identify(fa[x])!=-1)rotate(identify(x)==identify(fa[x])?fa[x]:x);pushup(x);}
inline void access(int x){
for(register int y=0;x;x=fa[y=x]){
splay(x);
if(rson)s[x].insert(mx[rson]);
rson=y;
if(y)s[x].erase(s[x].find(mx[y]));
pushup(x);
}
}
inline void makeroot(int x){access(x),splay(x);}
inline int findroot(int x){makeroot(x);while(lson)x=lson;splay(x);return x;}
inline void link(int x){splay(x),makeroot(pa[x]),fa[x]=pa[x],ch[1][pa[x]]=x,pushup(pa[x]);}
inline void cut(int x){access(x),splay(x),lson=fa[lson]=0,pushup(x);}
}lct[2];
struct edge{
int to,next;
}edge[200100];
void ae(int u,int v){
edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,head[v]=cnt++;
}
void dfs(int x,int fa){
pa[x]=fa;
for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dfs(edge[i].to,x);
}
int Q(int x){
int y=lct[col[x]].findroot(x);lct[col[x]].splay(y);
return lct[col[x]].mx[col[y]==col[x]?y:lct[col[x]].ch[1][y]];
}
void R(int x){
lct[col[x]].cut(x);
col[x]^=1;
lct[col[x]].link(x);
}
void C(int x,int y){
lct[0].makeroot(x),lct[0].val[x]=y,lct[0].pushup(x);
lct[1].makeroot(x),lct[1].val[x]=y,lct[1].pushup(x);
}
int main(){
scanf("%d",&n),memset(head,-1,sizeof(head));
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),ae(x,y);
for(int i=1;i<=n;i++)scanf("%d",&col[i]);
col[n+1]=2,lct[0].val[n+1]=lct[1].val[n+1]=0x80808080;
for(int i=1,x;i<=n;i++)scanf("%d",&x),lct[0].val[i]=lct[1].val[i]=x;
dfs(1,n+1);
// for(int i=1;i<=n;i++)printf("%d ",col[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",pa[i]);puts("");
for(int i=1;i<=n;i++)lct[col[i]].link(i);
scanf("%d",&m);
for(int i=1,x,y,z;i<=m;i++){
scanf("%d%d",&x,&y);
if(x==0)printf("%d\n",Q(y));
if(x==1)R(y);
if(x==2)scanf("%d",&z),C(y,z);
}
return 0;
}