From cfb007252904ba4a4a4805030d3e30f43b207174 Mon Sep 17 00:00:00 2001
From: zhouyuyang2002 <54274322+zhouyuyang2002@users.noreply.github.com>
Date: Tue, 27 Aug 2019 22:13:25 +0800
Subject: [PATCH] =?utf8?q?=E5=A2=9E=E5=8A=A0=E6=9C=80=E5=B0=8F=E7=93=B6?=
 =?utf8?q?=E9=A2=88=E8=B7=AF+kruscal=E9=87=8D=E6=9E=84=E6=A0=91?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 docs/graph/mst.md | 87 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 87 insertions(+)

diff --git a/docs/graph/mst.md b/docs/graph/mst.md
index 423b97ee..9ced06ee 100644
--- a/docs/graph/mst.md
+++ b/docs/graph/mst.md
@@ -464,3 +464,90 @@ int main() {
 ???+note "POJ 2395 Out of Hay"
     给出 n 个农场和 m 条边，农场按 1 到 n 编号，现在有一人要从编号为 1 的农场出发到其他的农场去，求在这途中他最多需要携带的水的重量，注意他每到达一个农场，可以对水进行补给，且要使总共的路径长度最小。
     题目要求的就是瓶颈树的最大边，可以通过求最小生成树来解决。
+
+## 最小瓶颈路
+
+### 定义
+
+无向图 $G$ 中 x 到 y 的最小瓶颈路是这样的一类简单路径，满足这条路径上的最大的边权在所有 x 到 y 的简单路径中是最小的。
+
+### 性质
+
+根据最小生成树定义，x 到 y 的最小瓶颈路上的最大边权等于最小生成树上 x 到 y 路径上的最大边权。虽然最小生成树不唯一，但是每种最小生成树 x 到 y 路径的最大边权相同且为最小值。也就是说，每种最小生成树上的 x 到 y 的路径均为最小瓶颈路。
+
+但是，并不是所有最小瓶颈路都存在一棵最小生成树满足其为树上 x 到 y 的简单路径。
+
+例如下图：
+
+[](./graph/mst5.png)
+
+1 到 4 的最小瓶颈路显然有以下两条： 1-2-3-4。 1-3-4。
+
+但是, 1-2 不会出现在任意一种最小生成树上。
+
+### 应用
+
+由于最小瓶颈路不唯一，一般情况下会询问最小瓶颈路上的最大边权。
+
+也就是说，我们需要求最小生成树链上的 max 。
+
+倍增，树剖都可以解决这里不再展开。
+
+## kruscal 重构树
+
+### 定义
+
+在跑 kruscal 的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。
+
+首先新建 n 个集合，每个集合恰有一个节点，点权为 $0$。
+
+每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将两个集合的根节点分别设为新建点的左儿子和右儿子。然后我们将两个集合和新建点合并成一个集合。将新建点设为根。
+
+不难发现，在进行 n-1 轮之后我们得到了一颗恰有 n 个叶子的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 kruscal 重构树。
+
+举个例子：
+
+![](./graph/mst5.png)
+
+这张图的 kruscal 重构树如下：
+
+![](./graph/mst6.png)
+
+### 性质
+
+不难发现，最小生成树上两个点之间的简单路径上边权最大值 = kruscal 重构树上两点之间的 LCA 的权值。
+
+也就是说，到点 $x$ 的简单路径上边权最大值 $\leq val$ 的所有点 $y$ 均在 kruscal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。
+
+我们在 kruscal 重构树上找到 $x$ 到根的路径上权值 $\leq val$ 的最浅的节点。显然这就是所有满足条件的节点所在的子树的根节点。
+
+!!! note "[CC MXMN](https://www.codechef.com/JULY19A/problems/MXMN)"
+    题目大意：给定两张 $n$ 个点 $2n$ 条边的联通无向带边权图，假设分别为G1,G2。
+
+    询问所有点对 $(i,j),(1 \leq i < j \leq n)$ 在两张图上的最小瓶颈路的最大边权的乘积的和。
+    
+    $n \leq 100000$
+
+我们首先求出两张图的最小生成树，并根据最小生成树构造 kruscal 重构树。
+
+我们可以在第一张图的最小生成树上运行点分治，预处理出来点分治中心到当前连通块所有点的链上最大值。
+
+现在我们将问题变成：
+
+> 给定一棵树
+> 多次询问，每次询问给定点集$S$和这个点集内的点权$v$。
+> 询问$\sum_{1 \leq i < j \leq |S|} \max(v_i,v_j) \times \max(edge_k|k 在 S_i 到 S_j的路径上)$
+
+此时我们可以直接建出第二张图的最小生成树的 kruscal 重构树。
+
+每次询问我们建出这个点集在 kruscal 重构树上形成的虚树。
+
+我们可以考虑在两个节点的 LCA 处对答案进行合并。
+
+我们采用动态开点线段树去维护点权在某段区间内的点的个数以及这些点的点权和。
+
+合并时我们可以通过判断左右儿子的相互关系来得出两个点权值之间的大小关系。这个过程可以在线段树合并的同时完成。
+
+也就是说，单次 $n$ 个节点的询问我们可以在 $O(n \log n)$ 的时间复杂度内解决。
+
+总时间复杂度 $O(n \log^2 n)$。
-- 
2.11.0