Steven_Meng's Blog

传送门

本质一样的一道YNOI

首先明确一件事情，这个换根其实是吓你的，

$1.$只有最近的一次换根才会对答案有影响（显然）

$2.$分情况讨论，我们始终以$1$节点为根，设现在查询的节点为$u$，上一次换根的根为$rt$（$rt$是一个假的根） ，我们画出$3$个图：

若$u==rt$，显然现在查询的是整棵树，对应到区间$[1,n]$：

若$LCA(u,rt)==u$（或者说$rt$在$u$的子树中），

我们想象一下，把$rt$从底下提上来，查询的就是红色圈圈起来的部分

再把这个红色圈圈起来的部分对应回去

原来就是整棵树去掉$v$的子树的部分，其中$v$为$u$的孩子，$rt$的祖先（可以树上倍增搞一下）

这个可以对应到两个区间$[1,L[v]-1]$，$[R[v]+1,n]$

最后一种情况，若$LCA(u,rt)!=u$，那么我们再画一个图：

发现这个换根和没换一样，所以就是查询区间$[L[u],R[u]]$

所以这道题我们就解决。。。。了吗？

首先，为了准确求出$dfn$ 序，我们要把$dfs2$魔改成这个样子

void dfs2(int u,int t){
    if (!u) return ;
    seq[L[u]=++cnt]=u;
    top[u]=t;
    dfs2(son[u],t);
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=son[u]&&v!=fa[u]){
            dfs2(v,v);
        }
    }
    R[u]=cnt;
}

然后，这道题还要有一个很孙的特判，如果$u==1||v==1$则返回根节点：

inline int LCA(int u,int v){
    if (u==1||v==1) return 1;
    if (dep[u]<dep[v]) swap(u,v);
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[v]){
            u=anc[u][i];
        }
    }
    if (u==v) return u;
    for (register int i=MAXM-1;i>=0;--i){
        if (anc[u][i]!=anc[v][i]){
            u=anc[u][i],v=anc[v][i];
        }
    }
    return anc[u][0];
}

献上$WA$无数次的代码：

#include <bits/stdc++.h>
#define MAXN 200005
#define MAXM 25
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int a[MAXN];
int fa[MAXN],dep[MAXN],top[MAXN],sz[MAXN],tofa[MAXN],son[MAXN];
int anc[MAXN][MAXM];
void dfs1(int u,int father){
    sz[u]=1;
    anc[u][0]=father;
    for (register int i=1;i<MAXM;++i){
        anc[u][i]=anc[anc[u][i-1]][i-1];
    }
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father){
            dep[v]=dep[u]+1;
            fa[v]=u;
            dfs1(v,u);
            sz[u]+=sz[v];
            if (sz[son[u]]<sz[v]) son[u]=v;
        }
    }
}
int L[MAXN],R[MAXN],seq[MAXN],cnt;
void dfs2(int u,int t){
    if (!u) return ;
    seq[L[u]=++cnt]=u;
    top[u]=t;
    dfs2(son[u],t);
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=son[u]&&v!=fa[u]){
            dfs2(v,v);
        }
    }
    R[u]=cnt;
}
inline int LCA(int u,int v){
    if (u==1||v==1) return 1;
    if (dep[u]<dep[v]) swap(u,v);
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[v]){
            u=anc[u][i];
        }
    }
    if (u==v) return u;
    for (register int i=MAXM-1;i>=0;--i){
        if (anc[u][i]!=anc[v][i]){
            u=anc[u][i],v=anc[v][i];
        }
    }
    return anc[u][0];
}
inline int Hop(int u,int lca){
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>dep[lca]) {
            u=anc[u][i];
        }
    }
    return u;
}
int val[MAXN];
namespace SegmentTree{
    struct node{
        int l,r;
        int mino,tag;
    }tree[MAXN<<1];
    #define lc i<<1
    #define rc i<<1|1
    inline void Cover(int i,int val){
        tree[i].mino=tree[i].tag=val;
    }
    inline void pushup(int i){
        tree[i].mino=min(tree[lc].mino,tree[rc].mino);
    }
    inline void pushdown(int i){
        if (tree[i].tag!=-1){
            Cover(lc,tree[i].tag);
            Cover(rc,tree[i].tag);
            tree[i].tag=-1;
        }
    }
    void Build(int i,int l,int r){
        tree[i].l=l,tree[i].r=r;
        tree[i].tag=-1;
        if (l==r){
            tree[i].mino=a[seq[l]];
            return ;
        }
        int mid=(l+r)>>1;
        Build(lc,l,mid);
        Build(rc,mid+1,r);
        pushup(i);
    }
    void Update(int i,int L,int R,int val){
        if (L<=tree[i].l&&tree[i].r<=R){
            Cover(i,val);
            return ;
        }
        int mid=(tree[i].l+tree[i].r)>>1;
        pushdown(i);
        if (L<=mid) Update(lc,L,R,val);
        if (mid<R) Update(rc,L,R,val);
        pushup(i);
    }
    int Query(int i,int L,int R){
        if (L<=tree[i].l&&tree[i].r<=R){
            return tree[i].mino;
        }
        int mid=(tree[i].l+tree[i].r)>>1,ans=0x7fffffff;
        pushdown(i);
        if (L<=mid) ans=min(ans,Query(lc,L,R));
        if (mid<R) ans=min(ans,Query(rc,L,R));
        return ans;
    }
}
using namespace SegmentTree;
inline void UpdateChain(int u,int v,int val){
    while (top[u]!=top[v]){
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        Update(1,L[top[u]],L[u],val);
        u=anc[top[u]][0];
    }
    if (dep[u]>dep[v]) swap(u,v);
    Update(1,L[u],L[v],val);
}
int main(){
    int n=read(),m=read();
    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    dfs1(1,0);
    dfs2(1,1);
    Build(1,1,n);
    int rt=read();
    while (m--){
        int opr=read();
        if (opr==1){
            rt=read();
        }
        else if (opr==2){
            int u=read(),v=read(),val=read();
            UpdateChain(u,v,val);
        }
        else if (opr==3){
            int u=read();
            if (u==rt){
                printf("%d\n",Query(1,1,n));
            }
            else if (LCA(u,rt)==u){
                int v=Hop(rt,u);
                printf("%d\n",min(Query(1,1,L[v]-1),Query(1,R[v]+1,n)));
            }
            else {
                printf("%d\n",Query(1,L[u],R[u]));
            }
        }
    }
}