Kruksal重构树

Author Avatar
Sakits 8月 07, 2018

简介

  在kruskal的基础上,处理一类关于无向图两点间路径上最值边权的问题。

建树

  将边按边权排序,如果边的两端不在同一并查集内则执行以下操作:
  每次不将边的两个端点直接连边,而是新建一个节点作为这两个节点的父亲节点,向这两个节点连边,并且自身点权为这条边的边权,以此建出一棵树。

for(int i=1;i<=m;i++)
{
    int fx=gf(q[i].x), fy=gf(q[i].y);
    if(fx==fy) continue;
    fa[fx]=fa[fy]=++tott;
    add(tott, fx); add(tott, fy);
    fa[tott]=tott; w[tott]=q[i].z;
}

性质

  1.1.显然点权满足堆性质,即根的点权比左右节点点权都大或都小
  2.2.原图两个点的路径上最小的最大边权/最大的最小边权为kruskal重构树上两点LCA的点权。

例题

1.1.bzoj3732:Network

  直接就是板子了。

2.2.bzoj5415:[Noi2018]归程

  对于一个限制,倍增跳到符合条件的深度最小的祖先,这个祖先的子树内即这个点能到达的所有点,预处理一下子树dist最小值就好了。

3.3.bzoj3551:[ONTAK2010]Peaks加强版

  和上个题一样,但是要维护子树内第kk大,搞个可持久化线段树合并就好了