求调

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100,INF=0x7fffffff;
struct segtree
{
    int mn,tag;
}s[N<<2];
struct edge{int y,n;}e[N<<1];
int n,m,head[N],cnt,val[N];
int dep[N],siz[N],f[N],son[N];
int id[N],rk[N],top[N],dfn,root0,root;
void ad(int x,int y)
{
    e[++cnt].n=head[x];
    e[cnt].y=y;
    head[x]=cnt;
}

void go1(int u,int fa)
{
    dep[u]=dep[fa]+1;
    f[u]=fa;
    siz[u]=1;
    for(int i=head[u];i;i=e[i].n)
    {
        int v=e[i].y;
        if(v==fa)continue;
        go1(v,u);
        if(siz[v]>siz[son[u]])
            son[u]=v;
        siz[u]+=siz[v];
    }

}

void go2(int u,int tp)
{
    id[u]=++dfn;
    rk[dfn]=u;
    top[u]=tp;
    if(son[u])
        go2(son[u],tp);
    for(int i=head[u];i;i=e[i].n)
    {
        int v=e[i].y;
        if(v==son[u] || dep[v]<dep[u])
            continue;
        go2(v,v);
    }
}

void pushup(int i){s[i].mn=min(s[i<<1].mn,s[i<<1|1].mn);}

void build(int i,int l,int r)
{
    s[i].tag=-1;
    if(l==r)
    {
        s[i].mn=val[rk[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
}

void pushdown(int i)
{
    if(s[i].tag=-1)return ;
    s[i<<1].tag=s[i<<1|1].tag=s[i].tag;
    s[i<<1].mn=s[i<<1|1].mn=s[i].tag;
    s[i].tag=-1;
}

void upd(int i,int l,int r,int x,int y,int z)
{
    if(l>=x && r<=y)
    {
        s[i].mn=s[i].tag=z;
        return ;
    }
    pushdown(i);
    int mid=(l+r)>>1;
    if(x<=mid)upd(i<<1,l,mid,x,y,z);
    if(y>mid)upd(i<<1|1,mid+1,r,x,y,z);
    pushup(i);
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=f[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    return y;
}

int jump(int x,int y)
{
    while(top[x]!=top[y])
    {
        x=top[x];
        if(f[x]==y)return x;
        x=f[x];
    }
    return son[y];
}

void ch(int x,int y,int v)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        upd(1,1,n,id[top[x]],id[x],v);
        x=f[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    upd(1,1,n,id[y],id[x],v);
}

int que(int i,int l,int r,int x,int y)
{
    if(l>=x && r<=y)
        return s[i].mn;
    pushdown(i);
    int mid=(l+r)>>1,num=INF;
    if(x<=mid)num=min(num,que(i<<1,l,mid,x,y));
    if(y>mid)num=min(num,que(i<<1|1,mid+1,r,x,y));
    return num;
}

void work()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        ad(x,y);
        ad(y,x);
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&val[i]);

    scanf("%d",&root0);
    root=root0;
    go1(root0,0);
    go2(root0,root0);
    build(1,1,n);

    while(m--)
    {
        int opt,x,y,v;
        scanf("%d%d",&opt,&x);
        if(opt==1)
            root=x;
        else if(opt==2)
        {
            scanf("%d%d",&y,&v);
            ch(x,y,v);
        }
        else
        {
            int ans=INF;
            if(x==root)
            {
                ans=s[1].mn;
                printf("%d\n",ans);
                continue;
            }
            if(id[x]>=id[root] && id[x]<id[root]+siz[root])
            {
                ans=que(1,1,n,id[x],id[x]+siz[x]-1);
                printf("%d\n",ans);
                continue;
            }
            int nw=lca(root,x);
            if(nw==x)
            {
                int z=jump(root,x);
                if(id[z]>1)
                ans=min(ans,que(1,1,n,1,id[z]-1));
                if(id[z]+siz[z]<=n)
                ans=min(ans,que(1,1,n,id[z]+siz[z],n));
                printf("%d\n",ans);
            }
            else
            {
                ans=que(1,1,n,id[x],id[x]+siz[x]-1);
                printf("%d\n",ans);
            }
        }
    }
}

int main()
{
    work();
    return 0;
}