【洛谷】【树链剖分】遥远的国度

题目链接:https://www.luogu.org/problemnew/show/P3979

思路:树链剖分+分类讨论

这题相比于普通的树链剖分,多了一个换根操作

但这依然难不倒我们

其实只要判断查询点与当前根的位置关系就可以了

$Case1$ 查询点的子树不包含根

这种情况答案与不换根的答案是一样的

$Case2$ 查询点在根上

这种情况的答案直接询问整棵树就可以了

$Case3$ 查询点的子树包含根

这时的答案就是除根所在子树之外点的答案

如何判断根在查询点的哪棵子树里呢?

利用$dfs$序判断即可

for(int i=h[x];i;i=a[i].li){
    if(a[i].nx!=fa[x]&&id[a[i].nx]<=id[root]&&id[a[i].nx]+siz[a[i].nx]-1>=id[root]){
        root就在这棵子树里;
    }
}

以下是完整代码↓

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=1<<17,INF=0x7fffffff;

int n,m,p,x,y,z,np,cnt,root;
int siz[MAXN],id[MAXN],h[MAXN],val[MAXN],ren[MAXN];
int fa[MAXN],sn[MAXN],tp[MAXN],top[MAXN];
int minn[MAXN<<1],chg[MAXN<<1];
struct rpg{
    int li,nx;
}a[MAXN<<1];

void add(int ls,int nx){
    a[++np]=(rpg){h[ls],nx};
    h[ls]=np;
}

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

void dfs1(int x,int f,int deep){
    tp[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int hwy=0;
    for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=f){
            dfs1(a[i].nx,x,deep+1);
            siz[x]+=siz[a[i].nx];
            if(siz[a[i].nx]>hwy){
                hwy=siz[a[i].nx];
                sn[x]=a[i].nx;
            }
        }
    }return;
}

void dfs2(int x,int tpx){
    top[x]=tpx;
    id[x]=++cnt;
    ren[cnt]=val[x];
    if(!sn[x]) return;
    dfs2(sn[x],tpx);
    for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=fa[x]&&a[i].nx!=sn[x]){
            dfs2(a[i].nx,a[i].nx);
        }
    }return;
}

void build(int k,int l,int r){
    chg[k]=-1;
    if(l==r){
        minn[k]=ren[l];
        return;
    }int i=k<<1,mid=l+r>>1;
    build(i,l,mid);
    build(i|1,mid+1,r);
    minn[k]=min(minn[i],minn[i|1]);
}

void po(int k,int l,int r){
    if(chg[k]==-1||l==r) return;
    int i=k<<1;
    chg[i]=chg[i|1]=chg[k];
    minn[i]=minn[i|1]=chg[k];
    chg[k]=-1;
}

void cchg(int k,int l,int r,int le,int ri,int x){
    po(k,l,r);
    if(le<=l&&r<=ri){
        minn[k]=x;
        chg[k]=x;
        return;
    }int i=k<<1,mid=l+r>>1;
    if(le<=mid) cchg(i,l,mid,le,ri,x);
    if(mid<ri) cchg(i|1,mid+1,r,le,ri,x);
    minn[k]=min(minn[i],minn[i|1]);
}

void ccchg(int x,int y,int z){
    while(top[x]!=top[y]){
        if(tp[top[x]]<tp[top[y]]) swap(x,y);
        cchg(1,1,n,id[top[x]],id[x],z);
        x=fa[top[x]];
    }if(tp[x]>tp[y]) swap(x,y);
    cchg(1,1,n,id[x],id[y],z);
    return;
}

int ask(int k,int l,int r,int le,int ri){
    if(le>ri) return INF;
    po(k,l,r);
    if(le<=l&&r<=ri) return minn[k];
    int i=k<<1,mid=l+r>>1;
    int ans=INF;
    if(le<=mid) ans=min(ans,ask(i,l,mid,le,ri));
    if(mid<ri) ans=min(ans,ask(i|1,mid+1,r,le,ri));
    return ans;
}

int asks(int x){
    if(x==root) return minn[1];
    if(id[root]>id[x]&&id[x]+siz[x]-1>=id[root]){
        for(int i=h[x];i;i=a[i].li){
            if(a[i].nx!=fa[x]&&id[a[i].nx]<=id[root]&&id[a[i].nx]+siz[a[i].nx]-1>=id[root]){
                return min(ask(1,1,n,1,id[a[i].nx]-1),ask(1,1,n,id[a[i].nx]+siz[a[i].nx],n));
            }
        }
    }return ask(1,1,n,id[x],id[x]+siz[x]-1);
}

void solve(){
    while(m--){
        scanf("%d",&p);
        if(p==1) scanf("%d",&x),root=x;
        else if(p==2) scanf("%d%d%d",&x,&y,&z),ccchg(x,y,z);
        else scanf("%d",&x),printf("%d\n",asks(x));
    }return;
}

int main(){
    init();
    dfs1(root,0,1);
    dfs2(root,root);
    build(1,1,n);
    solve();
    return 0;
}