90分求助

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read(){
    char ch=getchar();int x=0,f=1;
    while(ch<'0' || ch>'9') {
       if(ch=='-') f=-1;
      	  ch=getchar();
    }
    while(ch<='9' && ch>='0') {
       x=x*10+ch-'0';
       ch=getchar();
    }
    return x*f;
}

struct node{
    int l,r;
    ll add;
    ll mi;
}t[9040044];

int head[2002020],to[2020020],nxt[2020020];
int tot;

void add(int x,int y){
    tot++;
    to[tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}

int a[10100010];

int dfn[2020002],fa[2020020],top[2000202],hson[2002002],size[2020020],deep[2002020],rk[2002020];
int tim;

void dfs1(int x,int u){
    fa[x]=u;
    size[x]=1;
    deep[x]=deep[u]+1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==u) continue;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[hson[x]]){
            hson[x]=y;
        }
    }
}

void dfs2(int x,int tp){
    top[x]=tp;
    dfn[x]=++tim;
    rk[tim]=x;
    if(hson[x]==0) return ;
    dfs2(hson[x],tp);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa[x] || y==hson[x]) continue;
        dfs2(y,y);
    }
}

void build(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].mi=a[rk[l]];
        return ;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    t[p].mi=min(t[p<<1].mi,t[p<<1|1].mi);
}

void push(int p){
    if(t[p].add){
        t[p<<1].add=t[p<<1].mi=t[p<<1|1].add=t[p<<1|1].mi=t[p].add;
        t[p].add=0;
    }
}

void change(int p,int l,int r,ll v){
    if(l<=t[p].l && r>=t[p].r){
        t[p].add=v;
        t[p].mi=v;
        return;
    }
    push(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid) change(p<<1,l,r,v);
    if(r>mid) change(p<<1|1,l,r,v);
    t[p].mi=min(t[p<<1].mi,t[p<<1|1].mi);
}

void chainadd(int x,int y,ll v){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        change(1,dfn[top[x]],dfn[x],v);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    change(1,dfn[x],dfn[y],v);
}

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    return x;
}

ll qsum(int p,int l,int r){
    if(l<=t[p].l && r>=t[p].r){
        return t[p].mi;
    }
    int mid=t[p].l+t[p].r>>1;
    ll ans=1e16;
    if(l<=mid) ans=min(ans,qsum(p<<1,l,r));
    if(r>mid) ans=min(ans,qsum(p<<1|1,l,r));
    return ans;
}

int main(){
    int n=read(),m=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    int root=read();
    for(int i=1;i<=m;i++){
        int q=read();
        if(q==1){
            root=read();
        }
        if(q==2){
            int x=read(),y=read();
			ll v=read();
            chainadd(x,y,v);
        }
        if(q==3){
            int x=read();
            if(x==root) printf("%lld\n",t[1].mi);
            else{
                int lca=LCA(x,root);
                if(lca==x){
                    int y;
                    for(int i=head[x];i;i=nxt[i]){
                        int v=to[i];
                        if(dfn[v]<=dfn[root]&&dfn[v]+size[v]-1>=dfn[root]){
                            y=v;
                            break;
                        }
                    }
                    ll Ans=qsum(1,1,dfn[y]-1);
                    Ans=min(Ans,qsum(1,dfn[y]+size[y],n));
                    printf("%lld\n",Ans);
                }
                else printf("%lld\n",qsum(1,dfn[x],dfn[x]+size[x]-1));
            }
        }
    }
    return 0;
}