【SPOJ】—Qtree系列题解

Query on a tree

把边权丢给儿子就可以了
注意一下细节，其他的没什么
还有洛咕和 $SPOJ$ 要求不一样
这是洛咕的

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
    char ch=getchar();
    int res=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
    return res*f;
}
const int N=100005;
int adj[N],nxt[N<<1],to[N<<1],a[N],val[N<<1];
int n,cnt,tot;
char op[10];
inline void addedge(int u,int v,int w){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
}
int idx[N],top[N],dep[N],fa[N],pos[N],siz[N],son[N];
void dfs1(int u){
    siz[u]=1;
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa[u])continue;
        a[v]=val[e],fa[v]=u,dep[v]=dep[u]+1;
        dfs1(v),siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int tp){
    top[u]=tp,pos[u]=++tot,idx[tot]=u;
    if(son[u])dfs2(son[u],tp);
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
int tr[N<<2];
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
inline void pushup(int u){
    tr[u]=max(tr[lc],tr[rc]);
}
void build(int u,int l,int r){
    if(l==r){tr[u]=a[idx[l]];return;}
    build(lc,l,mid),build(rc,mid+1,r);
    pushup(u);
}
void update(int u,int l,int r,int p,int k){
    if(l==r){tr[u]=k;return;}
    if(p<=mid)update(lc,l,mid,p,k);
    else update(rc,mid+1,r,p,k);
    pushup(u);
}
int query(int u,int l,int r,int st,int des){
    if(st>des)return 0;
    if(st<=l&&r<=des)return tr[u];
    int res=0;
    if(st<=mid)res=max(res,query(lc,l,mid,st,des));
    if(mid<des)res=max(res,query(rc,mid+1,r,st,des));
    return res;
}
inline int pathquery(int u,int v){
    int res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res=max(res,query(1,1,n,pos[top[u]],pos[u]));
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    res=max(res,query(1,1,n,pos[u]+1,pos[v]));
    return res;
}
int U[N],V[N];
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        addedge(u,v,w),addedge(v,u,w);
        U[i]=u,V[i]=v;
    }
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    while(1){
        scanf("%s",op);
        if(op[0]=='Q'){
            int u=read(),v=read();
            cout<<pathquery(u,v)<<'
';
        }
        if(op[0]=='C'){
            int i=read(),k=read();
            if(fa[U[i]]==V[i])update(1,1,n,pos[U[i]],k);
            else update(1,1,n,pos[V[i]],k);
        }
        else if(op[0]=='D')break;
    }
}

Query on a tree II

SPOJ
洛咕
也很简单
边权记一下前缀和在 $lca$ 差分一下
第 $k$ 个倍增就可以了，处理一下在 $lca$ 的哪边

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
    char ch=getchar();
    int res=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
    return res*f;
}
const int N=100005;
int adj[N],nxt[N<<1],to[N<<1],a[N],val[N<<1],dep[N],dis[N];
int n,cnt,tot;
int f[N][22];
char op[10];
inline void addedge(int u,int v,int w){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
}
void dfs(int u){
    for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==f[u][0])continue;
        dis[v]=dis[u]+val[e],f[v][0]=u,dep[v]=dep[u]+1;dfs(v);
    }
}
inline int Lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    if(u==v)return u;
    for(int i=20;~i;i--){
        if(dep[f[u][i]]>=dep[v])u=f[u][i];
    }
    if(u==v)return u;
    for(int i=20;~i;i--){
        if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
    }
    return f[u][0];
}
inline int Kth(int u,int k){
    for(int i=20;~i;i--){
        if((1<<i)<=k){
            k-=(1<<i),u=f[u][i];
        }
    }
    return u;
}
int main(){
    int T=read();
    while(T--){
        memset(adj,0,sizeof(adj)),cnt=0;
        memset(f,0,sizeof(f));
        dis[1]=0;
        n=read();
        for(int i=1;i<n;i++){
            int u=read(),v=read(),w=read();
            addedge(u,v,w),addedge(v,u,w);
        }
        dfs(1);
        while(1){
            scanf("%s",op);
            if(op[0]=='D'&&op[1]=='I'){
                int u=read(),v=read();
                int lca=Lca(u,v);
                cout<<dis[u]+dis[v]-2*dis[lca]<<'
';
            }
            else if(op[0]=='K'){
                int u=read(),v=read();
                int k=read();
                int lca=Lca(u,v);
                if(dep[u]-dep[lca]+1>=k)cout<<Kth(u,k-1)<<'
';
                else cout<<Kth(v,dep[v]-dep[lca]-k+dep[u]-dep[lca]+1)<<'
';
            }
            else if(op[0]=='D'&&op[1]=='O')break;
        }
    }
}

Query on a tree again！

SPOJ
洛咕

树剖维护一下，把黑点权值当做1，线段树上二分查找一下最左边的就可以了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
    char ch=getchar();
    int res=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
    return res*f;
}
const int N=100005;
int adj[N],nxt[N<<1],to[N<<1],a[N],val[N<<1],dep[N],dis[N];
int tr[N<<2],plc[N<<2],cnt,tot,n,q;
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
int idx[N],top[N],fa[N],pos[N],siz[N],son[N];
inline void addedge(int u,int v){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
inline void pushup(int u){
    tr[u]=tr[lc]+tr[rc];
    plc[u]=tr[lc]?plc[lc]:(tr[rc]?plc[rc]:-1);
}
void update(int u,int l,int r,int p){
    if(l==r){tr[u]^=1,plc[u]=tr[u]?idx[l]:-1;return;}
    if(p<=mid)update(lc,l,mid,p);
    else update(rc,mid+1,r,p);
    pushup(u);
}
int query(int u,int l,int r,int st,int des){
    if(st>r||des<l)return -1;
    if(st<=l&&r<=des)return plc[u];
    int k=query(lc,l,mid,st,des);
    if(k==-1)return query(rc,mid+1,r,st,des);
    else return k;
}
void dfs1(int u){
    siz[u]=1;
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa[u])continue;
        dep[v]=dep[u]+1,fa[v]=u;
        dfs1(v),siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int tp){
    top[u]=tp,pos[u]=++tot,idx[tot]=u;
    if(son[u])dfs2(son[u],tp);
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
inline int pathquery(int u){
    int res=-1;
    while(top[u]!=1){
        int now=query(1,1,n,pos[top[u]],pos[u]);
        if(now!=-1)res=now;
        u=fa[top[u]];
    }
    int now=query(1,1,n,1,pos[u]);
    if(now!=-1)res=now;
    return res;
}
int main(){
    n=read(),q=read();
    memset(plc,-1,sizeof(plc));
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addedge(u,v),addedge(v,u);
    }
    dfs1(1),dfs2(1,1);
    while(q--){
        int op=read(),u=read();
        if(op==0){
            update(1,1,n,pos[u]);
        }
        else{
            cout<<pathquery(u)<<'
';
        }
    }
}

Query on a tree IV

SPOJ
洛咕

学习一下如何用 $Lct$ 维护子树信息

具体的是对于实儿子直接统计
对于虚儿子我们开一个 $set$ 来维护
发现影响虚实关系的只有 $access$
就在 $access$ 的时候加入原来的实儿子，删去现在的虚儿子的值

考虑处理三个数组 $lmx,rmx,mx$
$lmx$ 表示当前实链的顶部的点的最远的一个距离
$rmx$ 表示当前实链的底端的最远的一个距离
注意这2个玩意其实对于当前点的答案没用，只是为了给下一个父亲统计的
因为一颗辅助树其实维护就是一条深度递增的链
子树就是一段子链
$mx$ 则是经过当前点的最大答案

并维护 $2$ 个 $set:path、chain$ 分别表示子树的最大答案和子树最长的距离

考虑现在在辅助树中 $pushup$ 其实是把两条链的答案拼起来
顺带把虚子树也考虑进去
至于转移细节可以自己看
主要是讲一下个人的理解

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    int res=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
    return res*f;
}
const int N=200005;
const int inf=1e9;
int n,cnt,adj[N],nxt[N<<1],to[N<<1],val[N<<1],a[N],col[N],ans;
multiset<int> chain[N],path[N];
inline int fir(const multiset<int> &s){
    return s.empty()?-inf:*s.rbegin();
}
inline int sec(const multiset<int> &s){
    return s.size()<=1?-inf:*(++s.rbegin());
}
inline void addedge(int u,int v,int w){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
}
int lmx[N],rmx[N],mx[N],sum[N],w[N];
inline void chemx(int &a,int b){
    a=a>b?a:b;
}
namespace Lct{
    int q[N],son[N][2],fa[N];
    #define lc(u) son[u][0]
    #define rc(u) son[u][1]
    inline bool isrt(int u){
        if(!fa[u])return 1;
        return lc(fa[u])!=u&&rc(fa[u])!=u;
    }
    inline bool isrc(int u){
        return rc(fa[u])==u;
    }
    void pushup(int u){
        sum[u]=sum[lc(u)]+sum[rc(u)]+a[u];
        int cha=max(w[u],fir(chain[u]));
        int L=max(cha,rmx[lc(u)]+a[u]);
        int R=max(cha,lmx[rc(u)]);
        lmx[u]=max(lmx[lc(u)],sum[lc(u)]+a[u]+R);
        rmx[u]=max(rmx[rc(u)],sum[rc(u)]+L);
        mx[u]=max(rmx[lc(u)]+a[u]+R,lmx[rc(u)]+L);
        chemx(mx[u],max(mx[lc(u)],mx[rc(u)]));
        chemx(mx[u],fir(path[u]));
        chemx(mx[u],fir(chain[u])+sec(chain[u]));
        if(w[u]==0) chemx(mx[u],max(fir(chain[u]),0));
    }
    inline void rotate(int v){
        int u=fa[v],z=fa[u];
        int t=rc(u)==v;
        if(!isrt(u))son[z][rc(z)==u]=v;
        fa[v]=z;
        fa[son[v][t^1]]=u,son[u][t]=son[v][t^1];
        son[v][t^1]=u,fa[u]=v;
        pushup(u),pushup(v);
    }
    inline void splay(int u){
        while(!isrt(u)){
            if(!isrt(fa[u])){
                if(isrc(u)==isrc(fa[u]))rotate(fa[u]);
                else rotate(u);
            }
            rotate(u);
        }
        pushup(u);
    }
    inline void access(int u){
        for(int v=0;u;v=u,u=fa[u]){
            splay(u);
            if(rc(u))path[u].insert(mx[rc(u)]),chain[u].insert(lmx[rc(u)]);
            if(v)path[u].erase(path[u].find(mx[v])),chain[u].erase(chain[u].find(lmx[v]));
            rc(u)=v,fa[v]=u,pushup(u);
        }
    }
	void update(int u){
	    access(u),splay(u);
	    col[u]^=1,w[u]=col[u]?(-inf):0;
	    pushup(u),ans=mx[u];
	}
}
using namespace Lct;
void dfs(int u){
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa[u])continue;
        a[v]=val[e],fa[v]=u;
        dfs(v);
        chain[u].insert(lmx[v]),path[u].insert(mx[v]);
    }
    pushup(u);
}
char op[4];
int main(){
    n=read();
    for(int i=0;i<=n;i++)lmx[i]=rmx[i]=mx[i]=-inf;
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        addedge(u,v,w),addedge(v,u,w);
    }
    dfs(1);
    ans=mx[1];int q=read();
    while(q--){
        scanf("%s",op);
        if(op[0]=='A'){
            if(ans<0)puts("They have disappeared.");
            else cout<<ans<<'
';
        }
        else {int u=read();update(u);}
    }
}

Query on a tree V

SPOJ
洛咕

如果理解了 $4$ 的话其实5还要简单一些
还不是任意路径
还是 $lmn$ 表示实链顶端的点的最小答案
$rmn$ 表示实链底端的点最小答案
最后当前询问点已经到根了而且是链的最深点就可以直接输出 $rmx$ 就是了
（没明白的自己思考）

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    int res=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
    return res*f;
}
const int N=200005;
const int inf=1e9;
int n,cnt,adj[N],nxt[N<<1],to[N<<1],col[N],ans;
multiset<int> chain[N];
inline int fir(int u){
    return chain[u].size()?*chain[u].begin():inf;
}
inline void addedge(int u,int v){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
namespace Lct{
    int son[N][2],fa[N],lmn[N],rmn[N],siz[N];
    #define lc(u) son[u][0]
    #define rc(u) son[u][1]
    inline bool isrc(int u){
        return rc(fa[u])==u;
    }
    inline bool isrt(int u){
        return fa[u]?(lc(fa[u])!=u&&rc(fa[u])!=u):1;
    }
    inline void pushup(int u){
        siz[u]=siz[lc(u)]+siz[rc(u)]+1;
        lmn[u]=min(lmn[lc(u)],siz[lc(u)]+min((col[u]?0:inf),min(fir(u)+1,lmn[rc(u)]+1)));
        rmn[u]=min(rmn[rc(u)],siz[rc(u)]+min((col[u]?0:inf),min(fir(u)+1,rmn[lc(u)]+1)));
    }
    inline void rotate(int v){
        int u=fa[v],z=fa[u];
        int t=rc(u)==v;
        if(!isrt(u))son[z][rc(z)==u]=v;
        fa[v]=z;
        fa[son[v][t^1]]=u,son[u][t]=son[v][t^1];
        son[v][t^1]=u,fa[u]=v;
        pushup(u),pushup(v);
    }
    inline void splay(int u){
        while(!isrt(u)){
            if(!isrt(fa[u])){
                if(isrc(fa[u])==isrc(u))rotate(fa[u]);
                else rotate(u);
            }
            rotate(u);
        }
    }
    inline void access(int u){
        for(int v=0;u;v=u,u=fa[u]){
            splay(u);
            if(rc(u))chain[u].insert(lmn[rc(u)]);
            if(v)chain[u].erase(chain[u].find(lmn[v]));
            rc(u)=v;
            pushup(u);
        }
    } 
}
using namespace Lct;
void dfs(int u){
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa[u])continue;
        fa[v]=u,chain[u].insert(inf);
        dfs(v);
    }pushup(u);
}
int main(){
    n=read();lmn[0]=rmn[0]=inf;
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addedge(u,v),addedge(v,u);
    }
    dfs(1);
    int q=read();
    while(q--){
        int op=read(),u=read();
        if(op==1){
            access(u),splay(u);
            cout<<((rmn[u]>n)?-1:rmn[u])<<'
';
        }
        else{
            access(u),splay(u);
            col[u]^=1;pushup(u);
        }
    }
    return 0;
}

Query on a tree VI

SPOJ
洛咕

相当于维护树上联通块
一个直观的做法是维护2颗 $Lct$
每次枚举所有相邻点并连边
但显然复杂度不对

考虑类似将边权转点权的方式
把点的颜色转到边上
直接向父亲连边维护 $siz$ 就可以了

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    int res=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
    return res*f;
}
const int N=100005;
const int inf=1e9;
#define lc(u) son[u][0]
#define rc(u) son[u][1]
struct Lct{
    int q[N],son[N][2],siz[N],val[N],fa[N];
    inline bool isrc(int u){
        return rc(fa[u])==u;
    }
    inline bool isrt(int u){
        return fa[u]?(lc(fa[u])!=u&&rc(fa[u])!=u):1;
    }
    inline void pushup(int u){
        siz[u]=siz[lc(u)]+siz[rc(u)]+val[u]+1;
    }
    inline void rotate(int v){
        int u=fa[v],z=fa[u];
        int t=rc(u)==v;
        if(!isrt(u))son[z][rc(z)==u]=v;
        fa[v]=z;
        fa[son[v][t^1]]=u,son[u][t]=son[v][t^1];
        son[v][t^1]=u,fa[u]=v;
        pushup(u),pushup(v);
    }
    inline void splay(int u){
        while(!isrt(u)){
            if(!isrt(fa[u])){
                if(isrc(u)==isrc(fa[u]))rotate(fa[u]);
                else rotate(u);
            }
            rotate(u);
        }
        pushup(u);
    }
    inline void access(int u){
         for(int v=0;u;v=u,u=fa[u]){
         	splay(u);
         	if(rc(u))val[u]+=siz[rc(u)];
         	if(v)val[u]-=siz[v];
         	rc(u)=v,pushup(u);
         }
    }
    inline void link(int u,int v){
        splay(u),fa[u]=v;
        access(v),splay(v),siz[v]+=siz[u],val[v]+=siz[u];
    }
    inline void cut(int u,int v){
        access(u),splay(u);
        lc(u)=fa[lc(u)]=0;
        pushup(u);
    }
    inline int findrt(int u){
        access(u),splay(u);
        while(lc(u))u=lc(u);
        splay(u);return u;
    }
}T[2];
int n,cnt,adj[N],nxt[N<<1],to[N<<1],col[N],fa[N];
inline void addedge(int u,int v){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
void dfs(int u){
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa[u])continue;
        fa[v]=u,dfs(v),T[0].link(v,u);
    }
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addedge(u,v),addedge(v,u);
    }
    dfs(1),fa[1]=n+1,T[0].link(1,fa[1]);
    int m=read();
    while(m--){
        int op=read(),u=read();
        if(op==0){
            int v=T[col[u]].findrt(u);
            cout<<T[col[u]].siz[T[col[u]].rc(v)]<<'
';
        }
        else{
            T[col[u]].cut(u,fa[u]);
            T[col[u]^1].link(u,fa[u]);
            col[u]^=1;
        }
    }
}

Query on a tree

SPOJ
洛咕

求联通块最大值带修改
和上一道一样的套路
再像之前 $4、5$ 一样维护一个子树最大值就可以了

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    int res=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
    return res*f;
}
const int N=100005;
const int inf=2147483647;
#define lc(u) son[u][0]
#define rc(u) son[u][1]
int n,val[N],adj[N<<1],nxt[N<<1],to[N<<1];
inline void chemx(int &a,int b){
    a=a>b?a:b;
}
struct Lct{
    multiset<int> chain[N];
    inline int fir(int u){
        return chain[u].size()?*chain[u].rbegin():-inf;
    } 
    int mx[N],fa[N],son[N][2];
    Lct(){mx[0]=-inf;}
    inline bool isrc(int u){
        return rc(fa[u])==u;
    }
    inline bool isrt(int u){
        return fa[u]?(rc(fa[u])!=u&&lc(fa[u])!=u):1;
    }
    inline void pushup(int u){
        mx[u]=val[u];
        chemx(mx[u],max(mx[lc(u)],mx[rc(u)]));
        chemx(mx[u],fir(u));
    }
    inline void rotate(int v){
        int u=fa[v],z=fa[u];
        int t=rc(u)==v;
        if(!isrt(u))son[z][rc(z)==u]=v;
        fa[v]=z;
        fa[son[v][t^1]]=u,son[u][t]=son[v][t^1];
        son[v][t^1]=u,fa[u]=v;
        pushup(u),pushup(v);
    }
    inline void splay(int u){
        while(!isrt(u)){
            if(!isrt(fa[u])){
                if(isrc(fa[u]==isrc(u)))rotate(fa[u]);
                else rotate(u);
            }
            rotate(u);
        }
        pushup(u);
    }
    inline void access(int u){
        for(int v=0;u;v=u,u=fa[u]){
            splay(u);
            if(rc(u))chain[u].insert(mx[rc(u)]);
            if(v)chain[u].erase(chain[u].find(mx[v]));
            rc(u)=v,pushup(u);
        }
    }
    inline int findrt(int u){
        access(u),splay(u);
        while(lc(u))u=lc(u);
        splay(u);return u;
    }
    inline void link(int u,int v){
        splay(u);
        access(v),splay(v);
        fa[u]=v;
        rc(v)=u,pushup(v);
    }
    inline void cut(int u,int v){
        access(u),splay(u);
        fa[lc(u)]=0,lc(u)=0;
        pushup(u);
    }
    inline void update(int u,int k){
        access(u),splay(u);
        val[u]=k,pushup(u);
    }
    inline int query(int u){
        u=findrt(u);return mx[rc(u)];
    }
}T[2];
int fa[N],col[N],cnt;
inline void  addedge(int u,int v){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
void dfs(int u){
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa[u])continue;
        fa[v]=u,T[col[v]].link(v,u);
        dfs(v);
    }
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        addedge(u,v),addedge(v,u);
    }
    for(int i=1;i<=n;i++)col[i]=read();
    for(int i=1;i<=n;i++)val[i]=read();
    dfs(1),fa[1]=n+1;
    T[col[1]].link(1,fa[1]);
    int m=read();
    while(m--){
        int op=read(),u=read();
        if(op==0){
            cout<<T[col[u]].query(u)<<'
';
        }
        else if(op==1){
            T[col[u]].cut(u,fa[u]);
            col[u]^=1,T[col[u]].link(u,fa[u]);
        }
        else{
            int k=read();
            T[col[u]].update(u,k);
        }
    }
}

完结撒花~！