Kruskal重构树

spdarkle · 2023-09-30 16:54:11 · 个人记录

其实这玩意只是借用了Kruskal的思想而已。

解决问题：关于树上两点路径的带限制问题。

模版问题：多次询问，每次求从 u 出发，路径上所有边边权 \le d，可达的终点数量。

我们将每一条边简记为 (u_i,v_i,w_i)。现在，我们类比 Kruskal 算法进行 Kruskal 重构树的建立。

• 将每一条边按照 w_i 自小到大排序。
• 依次扫描每一条边。
• 对于 u_i,v_i 当前不属于同一个连通块的，设 u_i 所在连通块代表元为 U，设 v_i 所在连通块代表元为 V。
• 建立虚点 T，w_T=w_i，并连边 (T,U),(T,V)。
• 合并集合 U,V，新代表元为 T。

这样，我们最终得到了一颗含有 2n-1 个节点的二叉树。

此树具有以下性质：

• 树上的叶子节点代表原图点，非叶子节点均代表原图一条边。
• 对于任意非叶子节点 x，其任意祖先节点 y 都满足 w_y\ge w_x。
• 若原图为一棵树，则对于任意叶子节点 u,v，都满足 w_{LCA(u,v)} 为 u,v 之间简单路径的边的最大值。
• 若原图为一棵树，则对于任意叶子节点 u,v，都满足 LCA(u,v) 为其在重构树路径上的某一节点的叶子节点。

点权多叉重构树

事实上，在很多时候，我们用不上重构树是二叉树这一性质，并且建立它需要多倍常数，更是有些时候不方便操作——尤其是对于点权的操作。

涉及到点权操作，一般有两种处理方法。

法一

可以由题目条件将点权化为边权。譬如 CF1797F，限制经过的点权最小值，就可以通过 w(u,v)=\min(w_u,w_v) 进行转化。

法二

这是通法。

那么，我们新提出一种建立 Kruskal 重构树的方法。

我们按照各个点的权值，依次将各个点加入到重构树中。

我们以限制经过的点权最大值为例。

现将所有点按照点权从小到大排序，然后依次遍历点 u 的出边 v_i。

若已经在同一集合，则不用管，否则将 v_i 所在集合合并到 u 上，并将 u 与代表元 V 连接。

参考：

for(int u=1;u<=n;u++){//边权按照1~n依次递增。
    for(auto v:e[u]){
        if(v>u||u==find(v))continue;
        mx[u].push_back(find(v));
        f[find(v)]=u;
    }
}

最终建立出来的多叉重构树具有以下性质：

• 一般Kruskal重构树的性质。
• 若原图是一棵树，则对于任意重构树上的点 u,v，满足 u 是 v 的祖先，则有 w_u 是 path(u,v) 的最大值。

注意如果需要用到转为二叉树的性质，也是可以应用它的。

参考文献