bzoj3083 遙遠的國度 樹鍊剖分+lca

Description

zcwwzdjn在追殺十分sb的zhx，而zhx逃入了一個遙遠的國度。當zcwwzdjn準備進入遙遠的國度繼續追殺時，守護神RapiD阻攔了zcwwzdjn的去路，他需要zcwwzdjn完成任務後才能進入遙遠的國度繼續追殺。

問題是這樣的：遙遠的國度有n個城市，這些城市之間由一些路連接配接且這些城市構成了一顆樹。這個國度有一個首都，我們可以把這個首都看做整棵樹的根，但遙遠的國度比較奇怪，首都是随時有可能變為另外一個城市的。遙遠的國度的每個城市有一個防禦值，有些時候RapiD會使得某兩個城市之間的路徑上的所有城市的防禦值都變為某個值。RapiD想知道在某個時候，如果把首都看做整棵樹的根的話，那麼以某個城市為根的子樹的所有城市的防禦值最小是多少。由于RapiD無法解決這個問題，是以他攔住了zcwwzdjn希望他能幫忙。但zcwwzdjn還要追殺sb的zhx，是以這個重大的問題就被轉交到了你的手上。

對于20%的資料，n<=1000 m<=1000。

對于另外10%的資料，n<=100000，m<=100000，保證修改為單點修改。

對于另外10%的資料，n<=100000，m<=100000，保證樹為一條鍊。

對于另外10%的資料，n<=100000，m<=100000，沒有修改首都的操作。

對于100%的資料，n<=100000，m<=100000，0<所有權值<=2^31。

Solution

顯然是不能暴力換根的

先以1為預設根做一遍剖分，記查詢點為x，目前根為root，若lca(root,x)!=x就該怎麼做怎麼做，否則需要去掉x的子樹中包含root的那個再查詢

root=x特判整棵樹都要做

一開始少打else搞得輸入挂掉了，re半頁

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define fill(x,t) memset(x,t,sizeof(x))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
const int INF=;
const int N=;
const int E=;
using std:: swap;
struct edge{int x,y,next;}e[E];
int a[N],size[N],fa[N][],bl[N],dep[N],pos[N];
int mn[N<<],lazy[N<<];
int ls[N],edCnt=,n,m;
int read() {
    int x=,v=; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*+ch-'0',ch=getchar());
    return x*v;
}
void addEdge(int x,int y) {
    e[++edCnt]=(edge){x,y,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge){y,x,ls[y]}; ls[y]=edCnt;
}
void push_down(int now,int tl,int tr) {
    if (!lazy[now]||tl==tr) return;
    mn[now<<]=mn[now<<|]=lazy[now<<]=lazy[now<<|]=lazy[now];
    lazy[now]=;
}
void dfs1(int now) {
    rep(i,,) fa[now][i]=fa[fa[now][i-]][i-];
    size[now]=;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa[now][]) continue;
        dep[e[i].y]=dep[now]+;
        fa[e[i].y][]=now;
        dfs1(e[i].y);
        size[now]+=size[e[i].y];
    }
}
void dfs2(int now,int up) {
    pos[now]=++pos[]; bl[now]=up;
    int mx=;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y!=fa[now][]&&size[e[i].y]>size[mx]) mx=e[i].y;
    }
    if (!mx) return ;
    dfs2(mx,up);
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y!=fa[now][]&&e[i].y!=mx) dfs2(e[i].y,e[i].y);
    }
}
void modify(int now,int tl,int tr,int l,int r,int v) {
    if (l>r||l==||r==) return ;
    push_down(now,tl,tr);
    if (tl==l&&tr==r) {
        mn[now]=lazy[now]=v;
        return ;
    }
    int mid=(tl+tr)>>;
    if (r<=mid) modify(now<<,tl,mid,l,r,v);
    else if (l>mid) modify(now<<|,mid+,tr,l,r,v);
    else {
        modify(now<<,tl,mid,l,mid,v);
        modify(now<<|,mid+,tr,mid+,r,v);
    }
    mn[now]=min(mn[now<<],mn[now<<|]);
}
int query(int now,int tl,int tr,int l,int r) {
    if (l>r||l==||r==) return INF;
    push_down(now,tl,tr);
    if (tl==l&&tr==r) return mn[now];
    int mid=(tl+tr)>>;
    if (r<=mid) return query(now<<,tl,mid,l,r);
    else if (l>mid) return query(now<<|,mid+,tr,l,r);
    else {
        int ql=query(now<<,tl,mid,l,mid),qr=query(now<<|,mid+,tr,mid+,r);
        return min(ql,qr);
    }
}
void opt2(int x,int y,int v) {
    while (bl[x]!=bl[y]) {
        if (dep[bl[x]]<dep[bl[y]]) swap(x,y);
        modify(,,n,pos[bl[x]],pos[x],v);
        x=fa[bl[x]][];
    }
    if (dep[x]>dep[y]) swap(x,y);
    modify(,,n,pos[x],pos[y],v);
}
int get_lca(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);
    drp(i,,) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if (x==y) return x;
    drp(i,,) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][];
}
int get_son(int x,int y) {
    drp(i,,) if (dep[fa[x][i]]>dep[y]) x=fa[x][i];
    return x;
}
int main(void) {
    n=read(),m=read();
    rep(i,,n) {
        int x=read(),y=read();
        addEdge(x,y);
    }
    fill(mn,); dep[]=;
    dfs1(); dfs2(,);
    rep(i,,n) modify(,,n,pos[i],pos[i],read());
    int root=read();
    while (m--) {
        int opt=read();
        if (opt==) root=read();
        else if (opt==) {
            int x=read(),y=read(),v=read();
            opt2(x,y,v);
        } else {
            int x=read();
            if (x==root) printf("%d\n",query(,,n,,n));
            else if (get_lca(x,root)!=x) printf("%d\n",query(,,n,pos[x],pos[x]+size[x]-));
            else {
                int son=get_son(root,x),prt=INF;
                if (pos[son]>) prt=min(prt,query(,,n,,pos[son]-));
                if (pos[son]+size[son]<=n) prt=min(prt,query(,,n,pos[son]+size[son],n));
                printf("%d\n",prt);
            }
        }
    }
    return ;
}