【BZOJ3083】遙遠的國度 題解

題面：傳送門

    鍊上修改，子樹查詢，一看就是樹鍊剖分，鍊修改不需要說了吧，查詢 x x 的子樹隻需要查詢[posx,posx+sizex−1][posx,posx+sizex−1]即可。

    最難的也是最最關鍵的地方就是換根操作了。稍稍想一想就知道，不可能是真的換根，是以，我們要将換根操作轉化成别的東西。

    畫圖模拟一下，就會發現在目前根為 root r o o t ，查詢的子樹的根為 x x 的時候，有3種不同的情況：

    ①若x=rootx=root，直接查詢整棵樹即可。

    ②若在一開始的樹中， x x 為rootroot的祖先，答案為除了包含 root r o o t 的 x x 的子樹以外的所有點的最小值。

    ③否則，直接查詢原樹中xx的子樹。

    這道題就這樣做完了。

    時間複雜度： Θ(nlog22n) Θ ( n l o g 2 2 n ) 。

    全部代碼：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
using namespace std;
int val[];
int pos[];
int siz[];
int mymin(int x,int y)
{
    if(x==-)return y;
    if(y==-)return x;
    return min(x,y);
}
namespace sgt
{
    int mn[],root,cnt,son[][],lazy[];
    void pushup(int x)
    {
        mn[x]=min(mn[son[x][]],mn[son[x][]]);
    }
    void pushdown(int x)
    {
        if(lazy[x])
        {
            mn[x]=lazy[x];
            if(son[x][] && son[x][])lazy[son[x][]]=lazy[son[x][]]=lazy[x];
            lazy[x]=;
        }
    }
    void build(int &x,int l,int r)
    {
        x=++cnt;
        if(l==r)
        {
            mn[x]=val[l];
            return;
        }
        int mid=(l+r)>>;
        build(son[x][],l,mid);
        build(son[x][],mid+,r);
        pushup(x);
    }
    void update(int a,int b,int k,int l,int r,int v)
    {
        pushdown(k);
        if(a>r || b<l)return;
        if(a<=l && b>=r)
        {
            lazy[k]=v;
            pushdown(k);
        }
        else
        {
            int mid=(l+r)>>;
            update(a,b,son[k][],l,mid,v);
            update(a,b,son[k][],mid+,r,v);
            pushup(k);
        }
    }
    int query(int a,int b,int k,int l,int r)
    {
        pushdown(k);
        if(a>r || b<l)return -;
        if(a<=l && b>=r)return mn[k];
        int mid=(l+r)>>;
        int res=mymin(query(a,b,son[k][],l,mid),query(a,b,son[k][],mid+,r));
        pushup(k);
        return res;
    }
}
int n,m;
vector<int>G[],son[];
int d[];
int par[][];
int dep[];
int sps[];
void dfs(int x,int p)
{
    siz[x]=;
    for(int i=;i<G[x].size();i++)
    {
        int y=G[x][i];
        if(y==p)continue;
        son[x].push_back(y);
        par[y][]=x;
        dep[y]=dep[x]+;
        dfs(y,x);
        siz[x]+=siz[y];
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=;i>=;i--)if(dep[par[x][i]]>=dep[y])x=par[x][i];
    if(x==y)return x;
    for(int i=;i>=;i--)if(par[x][i]!=par[y][i])x=par[x][i],y=par[y][i];
    return par[x][];
}
int rt[];
int root;
int ind;
void HLD(int x,int lst)
{
    rt[x]=lst;
    pos[x]=++ind;
    val[ind]=d[x];
    if(sps[x])HLD(sps[x],lst);
    for(int i=;i<son[x].size();i++)if(son[x][i]!=sps[x])HLD(son[x][i],son[x][i]);
}
int gtka(int x,int k)
{
    for(int i=;i>=;i--)
    {
        if((<<i)<=k)
        {
            k-=(<<i);
            x=par[x][i];
        }
    }
    return x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=;i<=n;i++)scanf("%d",d+i);
    scanf("%d",&root);
    dep[]=-;
    dfs(,);
    for(int i=;i<=;i++)
    {
        for(int j=;j<=n;j++)par[j][i]=par[par[j][i-]][i-];
    }
    for(int i=;i<=n;i++)
    {
        for(int j=;j<son[i].size();j++)
        {
            if(!sps[i] || siz[son[i][j]]>siz[sps[i]])sps[i]=son[i][j];
        }
    }
    HLD(,);
    sgt::build(sgt::root,,n);
    int cur=;
    while(m--)
    {
        int op;
        scanf("%d",&op);
        if(op==)
        {
            int x;
            scanf("%d",&x);
            root=x;
        }
        else if(op==)
        {
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            int xy=lca(x,y);
            while(rt[x]!=rt[xy])
            {
                sgt::update(pos[rt[x]],pos[x],sgt::root,,n,v);
                x=par[rt[x]][];
            }
            sgt::update(pos[xy],pos[x],sgt::root,,n,v);
            while(rt[y]!=rt[xy])
            {
                sgt::update(pos[rt[y]],pos[y],sgt::root,,n,v);
                y=par[rt[y]][];
            }
            sgt::update(pos[xy],pos[y],sgt::root,,n,v);
        }
        else
        {
            cur++;
            int x;
            scanf("%d",&x);
            if(x==root)printf("%d\n",sgt::query(,n,sgt::root,,n));
            else if(pos[root]>=pos[x] && pos[root]<=pos[x]+siz[x]-)
            {
                int t=gtka(root,dep[root]-dep[x]-);
                printf("%d\n",mymin(sgt::query(,pos[t]-,sgt::root,,n),sgt::query(pos[t]+siz[t],n,sgt::root,,n)));
            }
            else printf("%d\n",sgt::query(pos[x],pos[x]+siz[x]-,sgt::root,,n));
        }
    }
    return ;
}