传送门
跟QTREE6QTREE6QTREE6神似，改成了求连通块里的最大值。
于是我们对每条链开一个heapheapheap维护一下即可。
MDMDMD终于1A1A1A链分治了。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
bool w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w^=1;ch=getchar();}
while(isdigit(ch))ans=(((ans<<2)+ans)<<1)+(ch^48),ch=getchar();
return w?ans:-ans;
}
typedef pair<int,int> pii;
const int N=1e5+5,inf=2e9;
int n,m,tot=0,num[N],pred[N],top[N],bot[N],fa[N],siz[N],hson[N],a[N];
vector<int>e[N];
bool col[N];
struct deletable_heap{
priority_queue<int>a,b;
inline void push(const int&x){a.push(x);}
inline void del(const int&x){b.push(x);}
inline int top(){while(b.size()&&a.top()==b.top())a.pop(),b.pop();return a.size()?a.top():-inf;}
inline int size(){return a.size()-b.size();}
}h[N][2];
void dfs1(int p){
siz[p]=1;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dfs1(v),siz[p]+=siz[v];
if(siz[v]>siz[hson[p]])hson[p]=v;
}
}
void dfs2(int p,int tp){
top[p]=tp,bot[tp]=p,pred[num[p]=++tot]=p;
if(!hson[p])return;
dfs2(hson[p],tp);
for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])!=fa[p]&&v!=hson[p])dfs2(v,v);
}
inline int max(const int&a,const int&b){return a>b?a:b;}
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
struct Val{
int ls,rs,f;
inline void init(const int&x){ls=rs=x,f=x==-inf?0:1;}
};
inline Val operator+(const Val&a,const Val&b){
Val ret;
ret.f=a.f&b.f;
ret.ls=a.f?max(a.ls,b.ls):a.ls;
ret.rs=b.f?max(b.rs,a.rs):b.rs;
return ret;
}
struct Node{int l,r;Val s[2];}T[N<<2];
inline void Set(int p){
int k=pred[T[p].l];
T[p].s[col[k]].init(max(h[k][col[k]].top(),a[k]));
T[p].s[col[k]^1].init(-inf);
}
inline void pushup(int p){
T[p].s[0]=T[lc].s[0]+T[rc].s[0];
T[p].s[1]=T[lc].s[1]+T[rc].s[1];
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r)return;
build(lc,l,mid),build(rc,mid+1,r);
}
inline void update(int p,int k){
if(T[p].l==T[p].r)return Set(p);
update(k<=mid?lc:rc,k),pushup(p);
}
inline Val query(int p,int ql,int qr,bool f){
if(ql<=T[p].l&&T[p].r<=qr)return T[p].s[f];
if(qr<=mid)return query(lc,ql,qr,f);
if(ql>mid)return query(rc,ql,qr,f);
return query(lc,ql,qr,f)+query(rc,ql,qr,f);
}
#undef lc
#undef rc
#undef mid
}
pii dfs3(int tp){
for(ri p=tp;p;p=hson[p]){
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p]||v==hson[p])continue;
pii tmp=dfs3(v);
h[p][0].push(tmp.fi),h[p][1].push(tmp.se);
}
SGT::update(1,num[p]);
}
return pii(SGT::query(1,num[tp],num[bot[tp]],0).ls,SGT::query(1,num[tp],num[bot[tp]],1).ls);
}
inline void update(int p){
int ft,bt,tp;
while(p){
ft=fa[top[p]],tp=top[p],bt=bot[tp];
if(ft){
h[ft][0].del(SGT::query(1,num[tp],num[bt],0).ls);
h[ft][1].del(SGT::query(1,num[tp],num[bt],1).ls);
}
SGT::update(1,num[p]);
if(ft){
h[ft][0].push(SGT::query(1,num[tp],num[bt],0).ls);
h[ft][1].push(SGT::query(1,num[tp],num[bt],1).ls);
}
p=ft;
}
}
inline int query(int p){
int ret,ft,tp,bt,x=p;
SGT::Val tmp;
while(p){
if(col[p]^col[x])return ret;
ft=fa[top[p]],tp=top[p],bt=bot[tp];
ret=SGT::query(1,num[p],num[bt],col[p]).ls;
if(p^tp){
tmp=SGT::query(1,num[tp],num[p]-1,col[p]);
ret=max(ret,tmp.rs);
if(!tmp.f)return ret;
}
p=ft;
}
return ret;
}
int main(){
n=read();
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
for(ri i=1;i<=n;++i)col[i]=read();
for(ri i=1;i<=n;++i)a[i]=read();
dfs1(1),dfs2(1,1),SGT::build(1,1,n),dfs3(1);
for(ri x,op,tt=read();tt;--tt){
op=read();
if(!op)cout<<query(read())<<'\n';
else if(op==1)col[x=read()]^=1,update(x);
else x=read(),a[x]=read(),update(x);
}
return 0;
}