[BZOJ 3083] 遥远的国度

Link：https://www.lydsy.com/JudgeOnline/problem.php?id=3083

Solution：

算是一道树剖的模板题吧

除了模板以外，新增的操作就是“换$root$”

此时我们分类讨论即可：

1、$x={root}$   查询$[1,n]$   （需要特判）

2、$x ot={lca(x,root)}$   直接查询子树即可，不受$root$变化的影响

3、$x={lca(x,root)}$   发现现在x的子树就是整棵树减去$x$往$root$方向向下最近的那个节点的子树，查询其补集即可

dfs序：

也是套路了，由于子树中dfs序连续，用dfs序整体维护子树（$root$为$x$的子树范围为$[L[x],R[x]]$）

若$x$往$root$方向最近的点为$v$，则除去其子树的补集为$[1,L[v]-1]+[R[v]+1,n]$

Code：

//by NewErA
#include <bits/stdc++.h>

using namespace std;
const int INF=2147483647;

#define mid (l+r)/2
#define lc k<<1,l,mid
#define rc k<<1|1,mid+1,r

const int MAXN=1e5+5;
int m,n,root=0,siz[MAXN],dep[MAXN],top[MAXN],f[MAXN][20],pos[MAXN],dat[MAXN],L[MAXN],R[MAXN],cnt=0;
int tag[5*MAXN],mn[5*MAXN],w[MAXN];
vector<int> a[MAXN];

void dfs1(int k)
{
    siz[k]=1;
    for(int i=1;(1<<i)<=dep[k];i++)  //最好将f在dfs1就更新掉，不能在处理完叶子结点后再更新
        f[k][i]=f[f[k][i-1]][i-1];    
    
    for(int i=0;i<a[k].size();i++)
    {
        if(a[k][i]==f[k][0]) continue;
        f[a[k][i]][0]=k;
        dep[a[k][i]]=dep[k]+1;
        
        dfs1(a[k][i]);
        
        siz[k]+=siz[a[k][i]];
    }
}

void dfs2(int k,int up)
{
    int bs=0;
    pos[k]=L[k]=++cnt,top[k]=up;
    for(int i=0;i<a[k].size();i++)
        if(a[k][i]!=f[k][0] && siz[a[k][i]]>siz[bs])
            bs=a[k][i];
    if(!bs){R[k]=L[k];return;}
    
    dfs2(bs,up);
    
    for(int i=0;i<a[k].size();i++)
        if(a[k][i]!=f[k][0] && a[k][i]!=bs)
            dfs2(a[k][i],a[k][i]);
    R[k]=cnt;
}

void push_up(int k){mn[k]=min(mn[k<<1],mn[k<<1|1]);}

void push_down(int k)
{
    if(tag[k])
    {
        tag[k<<1]=tag[k<<1|1]=tag[k];
        mn[k<<1]=mn[k<<1|1]=tag[k];
        tag[k]=0;
    }
}

void build(int k,int l,int r)
{
    if(l==r){mn[k]=w[l];return;}
    build(lc);build(rc);
    push_up(k);
}

void update_same(int a,int b,int x,int k,int l,int r)
{
    if(a<=l && r<=b)
    {
        mn[k]=tag[k]=x;
        return;
    }
    push_down(k);
    if(a<=mid) update_same(a,b,x,lc);
    if(b>mid) update_same(a,b,x,rc);
    push_up(k);
}

int query_min(int a,int b,int k,int l,int r)
{
    if(a<=l && r<=b) return mn[k];
    push_down(k);
    int ret=INF;
    if(a<=mid) ret=min(ret,query_min(a,b,lc));
    if(b>mid) ret=min(ret,query_min(a,b,rc));
    return ret;
}

void solve_same(int u,int v,int x)
{
    while (top[u]!=top[v])  //这里是while……
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        update_same(pos[top[u]],pos[u],x,1,1,n);
        u=f[top[u]][0];
    }
    if(pos[u]>pos[v]) swap(u,v);
    update_same(pos[u],pos[v],x,1,1,n);
}

int LCA(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=f[top[u]][0];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}

int find_nearest(int u,int depk)  //寻找x到root方向最近的节点
{
    int temp=dep[u]-depk;
    for(int i=0;i<=17;i++)
        if(temp&(1<<i)) u=f[u][i];
    return u;
}

int solve_max(int k)
{
    if(k==root) return query_min(1,n,1,1,n);  //特判
    else
    {
        int lca=LCA(k,root);
        if(lca!=k) return query_min(L[k],R[k],1,1,n);  //直接查询子树
        else
        {
            int nst=find_nearest(root,dep[k]+1);
            return min(query_min(1,L[nst]-1,1,1,n),query_min(R[nst]+1,n,1,1,n));
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        a[x].push_back(y);a[y].push_back(x);
    }
    for(int i=1;i<=n;i++) scanf("%d",&dat[i]);
    scanf("%d",&root);
    
    dfs1(root);dfs2(root,root);
    for(int i=1;i<=n;i++) w[pos[i]]=dat[i];
    build(1,1,n);
        
    for(int i=1;i<=m;i++)
    {
        int op,x,y,z;scanf("%d%d",&op,&x);
        if(op==1) root=x;
        else if(op==2) scanf("%d%d",&y,&z),solve_same(x,y,z);
        else printf("%d
",solve_max(x));
    }
    return 0;
}

Review：

1、整体维护子树，想到利用dfs序

2、犯的丝帛错误：

（1）将更新f数组的循环放到dfs2中处理完叶子结点后了，最好在dfs1中就更新掉

（2）线段树处理中将最外层的while打成if了……