[学习笔记]kruskal重构树 && 并查集重构树

Kruskal 重构树

[您有新的未分配科技点][BZOJ3545&BZOJ3551]克鲁斯卡尔重构树

kruskal是一个性质优秀的算法

加入的边是越来越劣的

科学家们借这个特点尝试搞一点事情。

kruskal求最小生成树的过程，如果把加入的一个边新建一个节点的话，并且把k1,k2的father设为新点的话，会得到一个2*n大小的树

实际上已经非常明白地表示kruskal这个过程了。这个树叫kruskal重构树

每个点的权值定义为所代表的边的权值。叶子节点权值最优。

由于贪心，所以树上所有点，从儿子到祖先权值单调不优。（这是最关键的性质）

树的结构我们非常熟悉

所以各种算法纷至沓来。

具体怎么用？

BZOJ3545 Peaks：

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走。

现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。N<=1e5,M,Q<=5*1e5

（不强制在线的话，直接离线排序+线段树合并或者启发式合并。（类似“永无乡”））

强制在线呢？

kruskal重构树登场！

对于只走小于x的边，会得到一个可以到达的联通块。

最小生成树的边上走，保证这个联通块是极大的。

联通块高度的第k大就是答案。

发现这个联通块对应重构树的一个子树！

重构树上，从v开始往上倍增找到最后一个权值小于等于x的点p

p对应的子树的叶子就是所有的联通块的点。（有点类似SAM的fail树？)

所以区间第k大，用dfs序处理一下，+主席树维护即可。

NOI2018归程

[NOI2018]归程

如果想到kruskal重构树（感觉学了应该都能想到，毕竟适用面也不是很广），那么这题就水了。

所能开车到达的集合里选择距离家最近的点下车。

kruskal重构树建出来（最大生成树），叶子赋予一个dis到1的距离。

dis用dij跑（因为出题人卡spfa）

然后dfs重构树处理信息，然后倍增处理询问。大功告成！

代码：

（很丑陋，见缝插针，而且mi、dep数组其实根本不需要）

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=+;

const int M=+;

const ll inf=0x3f3f3f3f3f3f3f3f;

ll dis[N];

ll ans[*N];

int val[*N];

int n,m;

struct node{

    int nxt,to;

    int val;

}e[*N];

int hd[*N],cnt;

void add(int x,int y,int z){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    e[cnt].val=z;

    hd[x]=cnt;

}

int tot;

namespace dij{

    bool vis[N];

    struct po{

        int x,d;

        po(int xx,int dd){

            x=xx;d=dd;

        }

        bool friend operator <(po a,po b){

            return a.d>b.d;

        }

    };

    priority_queue<po>q;

    void dij(){

        memset(vis,,sizeof vis);

        memset(dis,0x3f,sizeof dis);

        while(!q.empty()) q.pop();

        dis[]=;

        q.push(po(,));

        while(!q.empty()){

            po now=q.top();q.pop();

            if(vis[now.x]) continue;

            vis[now.x]=;

            dis[now.x]=now.d;

            for(reg i=hd[now.x];i;i=e[i].nxt){

                int y=e[i].to;

                if(vis[y]) continue;

                q.push(po(y,dis[now.x]+e[i].val));

            }

        }

        for(reg i=;i<=n;++i){

            ans[i]=dis[i];

            //mi[i][0]=0x3f3f3f3f;

        }

    }

}

struct edge{

    int x,y;

    int l,a;

    bool friend operator <(edge a,edge b){

        return a.a>b.a;

    }

}b[M];

//represent the value of edge

namespace kruscal{

    int fa[*N];

    int fin(int x){

        return fa[x]==x?x:fa[x]=fin(fa[x]);

    }

    void main(){

        for(reg i=;i<=n;++i) {

            fa[i]=i;val[i]=0x3f3f3f3f;

        }

        tot=n;

    //    cout<<" tot "<<tot<<endl;

        sort(b+,b+m+);

        for(reg i=;i<=m;++i){

            int k1=fin(b[i].x),k2=fin(b[i].y);

        //    cout<<" bb "<<tot<<" "<<i<<" : "<<b[i].x<<" "<<b[i].y<<" rt "<<k1<<"  sand "<<k2<<endl;

            if(k1!=k2){

                ++tot;

                fa[tot]=tot;

                ans[tot]=inf;

                add(tot,k1,);

                add(tot,k2,);

                fa[k1]=fa[k2]=tot;

                val[tot]=b[i].a;

            }

        }

    }

}

int fa[*N][];

int mi[*N][];

int dep[*N];

void dfs(int x,int d){

    dep[x]=d;

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        fa[y][]=x;

        mi[y][]=min(val[y],val[x]);

        dfs(y,d+);

        ans[x]=min(ans[x],ans[y]);

    }

}

ll query(int x,int p){

    for(reg j=;j>=;--j){

        if(fa[x][j]){

            if(mi[x][j]>p) x=fa[x][j];

        }

    }

    return ans[x];

}

void clear(){

    memset(fa,,sizeof fa);

    memset(mi,0x3f,sizeof mi);

    memset(dep,,sizeof dep);

    memset(hd,,sizeof hd);

    cnt=;

}

int main(){

    int T;

    rd(T);

    while(T--){

        rd(n);rd(m);

        clear();

        for(reg i=;i<=m;++i){

            rd(b[i].x);rd(b[i].y);rd(b[i].l);rd(b[i].a);

            add(b[i].x,b[i].y,b[i].l);

            add(b[i].y,b[i].x,b[i].l);

        }

        dij::dij();

    //    cout<<" after dij "<<endl;

        memset(hd,,sizeof hd);

        cnt=;

        kruscal::main();

    //    cout<<" after kruc "<<endl;

        dfs(tot,);

//        cout<<" after dfs "<<endl;

        for(reg j=;j<=;++j){

            for(reg i=;i<=tot;++i){

                fa[i][j]=fa[fa[i][j-]][j-];

                mi[i][j]=min(mi[i][j-],mi[fa[i][j-]][j-]);

            }

        }

//        cout<<" tot "<<tot<<endl;

//        for(reg i=1;i<=tot;++i){

//            cout<<" ii "<<i<<" val "<<val[i]<<" ans "<<ans[i]<<" fafa "<<fa[i][0]<<endl;

//        }

        int q,k,s;

        rd(q);rd(k);rd(s);

        ll las=;

        int v,p;

        while(q--){

            rd(v);rd(p);

            v=(v+k*las-)%n+;

            p=(p+k*las)%(s+);

            printf("%lld\n",las=query(v,p));

        }

    }

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/1/8 18:49:37

*/

这个算法适用面：
在线处理询问在经过小于（大于）某个边权的边所能到的集合里的信息。

主要性质是祖先权值的单调不优。

这个算法是对kruskal求最小生成树的操作过程的树形结构化，从而精确剖析过程，使得维护方便。

有异曲同工之妙的是动态点分治的分治树，也是对操作过程的树形结构化。

还有一个例题：（NOI和IOI都考了诶热度真高）

[IOI2018] werewolf 狼人

upda：2019.2.13

并查集重构树

除了Kruskal重构树之外，还有一个东西叫做并查集重构树

引入例题

n个点，q次操作，每次加入一条边（不会重边自环），或者查询两个点最早什么时候连通

n,q<=1e5

（某次jzoj考试题）

还是考虑具体维护出操作的结构

用按秩合并并查集，边权就是这次加入的边的时间值

发现，两个点第一次连通，一定是两个点并查集上路径最大值！

由于按秩合并，树高logn，可以暴力查询

如果是最后询问，可以建倍增数组，loglogn复杂度

对于一般的图，边权sort，然后按照上述做即可

毒瘤一些：

1.sort用松式基排

2.并查集按秩合并+路径压缩，另外开一个邻接表记录树

接近O(n)

性质：
1.越靠上权值越劣

2.两点间最大权值就是连通时间

比较优劣

并查集重构树：

劣势：子树不是一个区间（因为没有附加点）

优势：空间小，好写好调，两点间信息可以O(loglogn)快速求出。

kruskal重构树：

反过来。

劣势：难写一些，容易写错。

优势：多了附加点，经过小于vi的边到达的区域是子树，加上dfn序列很好维护。

巴特西