BZOJ3083 遥远的国度（树链剖分+线段树）

　　考虑暴力树剖。那么修改路径和查询子树最小值非常简单。

　　对于换根当然不能真的给他转一下，我们只记录当前根是哪个。对于查询，如果查询点不在当前根到原根的路径上，显然换根是对答案没有影响的；如果是当前根，答案就是整棵树最小值，否则即是要查询该路径上的后代所在子树外的点的最小值，去掉这段区间就可以了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 100010

#define int unsigned int

#define inf 2147483649

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,root,p[N],a[N],t=,cnt=;

int dfn[N],id[N],fa[N],son[N],deep[N],size[N],top[N];

int L[N<<],R[N<<],tree[N<<],lazy[N<<];

struct data{int to,nxt;

}edge[N<<];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void dfs1(int k)

{

    size[k]=;

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=fa[k])

    {

        deep[edge[i].to]=deep[k]+;

        fa[edge[i].to]=k;

        dfs1(edge[i].to);

        size[k]+=size[edge[i].to];

        if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to;

    }

}

void dfs2(int k,int from)

{

    id[k]=++cnt;dfn[cnt]=k;

    top[k]=from;

    if (son[k]) dfs2(son[k],from);

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=fa[k]&&edge[i].to!=son[k])

    dfs2(edge[i].to,edge[i].to);

}

void build(int k,int l,int r)

{

    L[k]=l,R[k]=r;

    if (l==r) {tree[k]=a[dfn[l]];return;}

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    tree[k]=min(tree[k<<],tree[k<<|]);

}

void down(int k)

{

    tree[k<<]=tree[k<<|]=lazy[k];

    lazy[k<<]=lazy[k<<|]=lazy[k];

    lazy[k]=;

}

void up(int k){tree[k]=min(tree[k<<],tree[k<<|]);}

int query(int k,int l,int r)

{

    if (l>r) return inf;

    if (L[k]==l&&R[k]==r) return tree[k];

    if (lazy[k]) down(k);

    int mid=L[k]+R[k]>>;

    if (r<=mid) return query(k<<,l,r);

    else if (l>mid) return query(k<<|,l,r);

    else return min(query(k<<,l,mid),query(k<<|,mid+,r));

}

void modify(int k,int l,int r,int x)

{

    if (L[k]==l&&R[k]==r) {tree[k]=lazy[k]=x;return;}

    if (lazy[k]) down(k);

    int mid=L[k]+R[k]>>;

    if (r<=mid) modify(k<<,l,r,x);

    else if (l>mid) modify(k<<|,l,r,x);

    else modify(k<<,l,mid,x),modify(k<<|,mid+,r,x);

    up(k);

}

void jump_modify(int x,int y,int z)

{

    while (top[x]!=top[y])

    {

        if (deep[top[x]]<deep[top[y]]) swap(x,y);

        modify(,id[top[x]],id[x],z);

        x=fa[top[x]];

    }

    if (deep[x]<deep[y]) swap(x,y);

    modify(,id[y],id[x],z);

}

int getans(int k)

{

    if (k==root) return query(,,n);

    int x=k,y=root;

    while (top[x]!=top[y])

    {

        if (deep[top[x]]<deep[top[y]]) swap(x,y);

        x=fa[top[x]];

    }

    if (deep[x]<deep[y]) swap(x,y);

    if (k==y)

    {

        for (int i=p[k];i;i=edge[i].nxt)

        if (id[edge[i].to]<=id[root]&&id[root]<=id[edge[i].to]+size[edge[i].to]-)

        return min(query(,,id[edge[i].to]-),query(,id[edge[i].to]+size[edge[i].to],n));

    }

    else return query(,id[k],id[k]+size[k]-);

}

signed main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3083.in","r",stdin);

    freopen("bzoj3083.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<n;i++)

    {

        int x=read(),y=read();

        addedge(x,y),addedge(y,x);

    }

    for (int i=;i<=n;i++) a[i]=read();

    dfs1();

    dfs2(,);

    build(,,n);

    root=read();

    while (m--)

    {

        int op=read();

        if (op==) root=read();

        else if (op==) printf("%d\n",getans(read()));

        else

        {

            int x=read(),y=read(),z=read();

            jump_modify(x,y,z);

        }

    }

    return ;

}