bzoj 3083: 遙遠的國度

題意：

維護一棵樹，支援換根，路徑修改，目前根下的子樹最小值。

題解：

首先可以發現換根沒什麼太大的用處，無論換了幾次，隻有最後一次是對目前有影響的。是以記錄下現在哪個做根，樹的形态不用動。

第二種操作直接樹剖。

關鍵是查詢，因為換根，有點麻煩。

假設整棵樹一開始的根是1，那麼當x做根時，隻對x到1的路徑上的點的子樹産生影響。

那麼其他點就直接dfs序化成區間求最值。

當一個點y是x的祖宗，那麼它的子樹就變成這樣：

右上角為y的子樹。

是以找到y到x的路徑的第一個點，除去這棵子樹其他就區間的最值就是答案。

code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
struct trnode{
    int fa,dep,son,tot,top,lc,rc,c,la,u;
}tr[];int ys[],z=,tot=,rt;
struct node{
    int y,next;
}a[];int len=,last[];
int n,m;
int read()
{
    int x=,f=;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void ins(int x,int y)
{
    a[++len].y=y;
    a[len].next=last[x];last[x]=len;
}
void pre_node(int x,int fa)
{
    tr[x].dep=tr[fa].dep+;tr[x].fa=fa;tr[x].tot=;
    for(int i=last[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(y==fa) continue;
        pre_node(y,x);
        if(tr[tr[x].son].tot<tr[y].tot) tr[x].son=y;
        tr[x].tot+=tr[y].tot;
    }
}
void pre_edge(int x,int top)
{
    tr[x].top=top;ys[x]=tr[x].la=++z;
    if(tr[x].son!=) pre_edge(tr[x].son,top),tr[x].la=tr[tr[x].son].la;
    for(int i=last[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(y==tr[x].fa||y==tr[x].son) continue;
        pre_edge(y,y);
        tr[x].la=tr[y].la;
    }
}
int bt(int l,int r)
{
    int x=++tot;
    if(l!=r)
    {
        int mid=(l+r)/;
        tr[x].lc=bt(l,mid);
        tr[x].rc=bt(mid+,r);
    }
    return x;
}
void update(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc,c=tr[x].u;
    tr[lc].c=tr[rc].c=c;
    tr[lc].u=tr[rc].u=c;
    tr[x].u=;
}
void change(int x,int l,int r,int fl,int fr,int c)
{
    if(l==fl&&r==fr){tr[x].c=tr[x].u=c;return;}
    int mid=(l+r)/;
    if(tr[x].u!=) update(x);
    if(fr<=mid) change(tr[x].lc,l,mid,fl,fr,c);
    else if(fl>mid) change(tr[x].rc,mid+,r,fl,fr,c);
    else change(tr[x].lc,l,mid,fl,mid,c),change(tr[x].rc,mid+,r,mid+,fr,c);
    tr[x].c=min(tr[tr[x].lc].c,tr[tr[x].rc].c);
}
int findans(int x,int l,int r,int fl,int fr)
{
    if(l==fl&&r==fr) return tr[x].c;
    int mid=(l+r)/;
    if(tr[x].u!=) update(x);
    if(fr<=mid) return findans(tr[x].lc,l,mid,fl,fr);
    if(fl>mid) return findans(tr[x].rc,mid+,r,fl,fr);
    return min(findans(tr[x].lc,l,mid,fl,mid),findans(tr[x].rc,mid+,r,mid+,fr));
}
void solve(int x,int y,int c)
{
    int tx=tr[x].top,ty=tr[y].top;
    while(tx!=ty)
    {
        if(tr[tx].dep<tr[ty].dep) swap(x,y),swap(tx,ty);
        change(,,n,ys[tx],ys[x],c);
        x=tr[tx].fa,tx=tr[x].top;
    }
    if(tr[x].dep<tr[y].dep) swap(x,y);
    change(,,n,ys[y],ys[x],c);
}
bool check(int x,int y)//判斷x是否為y的祖宗
{
    if(tr[x].dep>tr[y].dep) return false;
    int ty=tr[y].top;
    while(tr[ty].dep>tr[x].dep)
        y=tr[ty].fa,ty=tr[y].top;
    return tr[x].top==ty;
} 
void work(int x)
{
    if(rt==||!check(x,rt)){printf("%d\n",findans(,,n,ys[x],tr[x].la));return;}
    if(x==rt){printf("%d\n",findans(,,n,,n));return;}
    int y=rt,ty=tr[y].top,tx=tr[x].top;
    while(ty!=tx&&tr[ty].fa!=x)
        y=tr[ty].fa,ty=tr[y].top;
    if(tx==ty) ty=tr[x].son;
    int l=ys[ty],r=tr[ty].la;
    int ans=(<<);
    if(l!=) ans=min(ans,findans(,,n,,l-));
    if(r!=n) ans=min(ans,findans(,,n,r+,n));
    printf("%d\n",ans);
}
int main()
{
    n=read();m=read();
    for(int i=;i<n;i++)
    {
        int x,y;x=read();y=read();
        ins(x,y);ins(y,x);
    }
    pre_node(,);pre_edge(,);
    bt(,n);
    for(int i=;i<=n;i++)
    {
        int c;c=read();
        change(,,n,ys[i],ys[i],c);
    }
    rt=read();
    while(m--)
    {
        int opt;opt=read();
        if(opt==) rt=read();
        if(opt==)
        {
            int x,y,c;x=read();y=read();c=read();
            solve(x,y,c);
        }
        if(opt==)
        {
            int x;x=read();
            work(x);
        }
    }
}