天天看點

BZOJ 3083 遙遠的國度 樹鍊剖分 線段樹

傳送門

//各位不要吐槽我寫水題的題解

題目大意:

給你一棵有點權的有根樹,進行三種操作

1.換根

2.改變某兩點間簡單路徑上的權值為一個指定值

3.查詢在目前根的情況下,點x及其子樹的點權最小值

大概如果不換根,這就是道水題了,隻需要樹鍊剖分。

乍一看可能認為他是一道動态樹問題,但是其實并沒有那麼麻煩

我們不妨先按最開始的根進行剖分,然後進行讨論

設查詢的點為x,目前的根為root

假設以原來的根為根,我們令L=lca(root,x),那麼我們就可以讨論幾種情況

1.root=x

     顯然,這是我們應該查詢整棵樹,線段樹的第一段的值直接輸出就行

2.L!=x

      說明x并不在原根到目前根的路徑上,直接查詢x的整棵子樹就行了

3.L=x

      随手畫一下,我們會發現這時x所管轄的區間是非root鍊的區間,其實就是求他下面的

與root相連的那個兒子及其子樹的補集。直接維護就行了這時我們會發現,已經包括了所有的情況下面是一張圖,幫助了解

BZOJ 3083 遙遠的國度 樹鍊剖分 線段樹
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#define N 100000+5
#define M 400000+5
const long long inf = ll;
using namespace std;
int head[N];
inline long long read()
{
    int x=,f=;char ch =getchar();
    while(ch <'0' || ch >'9'){if(ch == '-')f=-;ch = getchar();}
    while(ch >='0'&& ch<='9'){x=(x<<)+(x<<)+ch-'0';ch = getchar();}
    return x*f;
}
struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];
inline void add(int x,int y)
{
    static int cnt = ;
    edge[++cnt] = graph(head[x],y);
    head[x]=cnt;
    edge[++cnt] = graph(head[y],x);
    head[y]=cnt;
}
int fa[N],size[N],w[N],top[N],depth[N],sz,last[N];
void DFS1(int x)
{
    size[x]=;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa[x])
        {
            fa[edge[i].to]=x;
            depth[edge[i].to]=depth[x]+;
            DFS1(edge[i].to);
            size[x]+=size[edge[i].to];
        }
}
void DFS2(int x,int chain)
{
    top[x]=chain,w[x]=last[x]=++sz;
    int k = ;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa[x]&&size[k]<size[edge[i].to])
            k=edge[i].to;
    if(!k)return;
    DFS2(k,chain);last[x]=max(last[x],last[k]);
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa[x]&&edge[i].to!=k)
            DFS2(edge[i].to,edge[i].to),last[x]=max(last[x],last[edge[i].to]);
}
struct seg
{
    int l,r;
    long long mn;
    long long lazy;
}tr[M];
void build(int k,int l,int r)
{
    tr[k].l=l,tr[k].r=r,tr[k].lazy=inf;
    if(l==r)return;
    int mid = (l+r)>>;
    build(k<<,l,mid);build(k<<|,mid+,r);
}
inline void updata(int k)
{
    tr[k].mn = min(tr[k<<].mn,tr[k<<|].mn);
}
inline void down(int k)
{
    long long tmp = tr[k].lazy;tr[k].lazy=inf;
    if(tr[k].l==tr[k].r || tmp==inf)return;
    tr[k<<].lazy=tr[k<<|].lazy=tr[k<<].mn=tr[k<<|].mn=tmp;
}
void change(int k,int l,int r,long long x)
{
    down(k);
    if(tr[k].l==l && tr[k].r==r){tr[k].mn=tr[k].lazy=x;return;}
    int mid = (tr[k].l+tr[k].r)>>;
    if(r<=mid)change(k<<,l,r,x);
    else if(l>mid)change(k<<|,l,r,x);
    else change(k<<,l,mid,x),change(k<<|,mid+,r,x);
    updata(k);
}
long long ask(int k,int l,int r)
{
    down(k);
    if(l==tr[k].l && r==tr[k].r)return tr[k].mn;
    int mid = (tr[k].l+tr[k].r)>>;
    if(r<=mid)return ask(k<<,l,r);
    else if(l>mid)return ask(k<<|,l,r);
    else return min(ask(k<<,l,mid),ask(k<<|,mid+,r));
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return depth[x]<depth[y]?x:y;
}
void solvechange(int x,int y,long long z)
{
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]])swap(x,y);
        change(,w[top[x]],w[x],z); x=fa[top[x]];
    }
    if(depth[x]>depth[y])swap(x,y);
    change(,w[x],w[y],z);
}
long long val[N];
int main()
{
    int n=read(),m=read();
    for(int i=;i<n;++i)
    {
        int x=read(),y=read();
        add(x,y);
    }
    DFS1();
    DFS2(,);
    build(,,n);
    for(int i=;i<=n;++i)
        val[i]=read();
    int tt=read();
    for(int i=;i<=n;++i)
        change(,w[i],w[i],val[i]);
    for(int i=;i<=m;++i)
    {
        int op = read();
        if(op==)
            tt=read();
        else if(op==)
        {
            int x=read(),y=read(),z=read();
            solvechange(x,y,z);
        }
        else
        {
            int x=read();
            int L = lca(x,tt);
            if(x==tt)
            {
                printf("%lld\n",tr[].mn);
            }
            else if(L!=x)
            {
                printf("%lld\n",ask(,w[x],last[x]));
            }
            else
            {
                int v;
                for(int i=head[x];i;i=edge[i].next)
                    if(w[tt]>=w[edge[i].to]&&w[tt]<=last[edge[i].to]&&edge[i].to!=fa[x])
                        v=edge[i].to;
                long long ans = inf;
                if(w[v]>=)
                    ans = min(ans,ask(,,w[v]-));
                if(last[v]<n)
                    ans = min(ans,ask(,last[v]+,n));
                printf("%lld\n",ans);
            }
        }
    }
}
           
BZOJ 3083 遙遠的國度 樹鍊剖分 線段樹