wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

图论

图的连通性

有向图的强连通分量

无向图的割点割边和双连通分量

流和匹配

最大流

最大流的一些应用

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

[[ item.c ]]

kruskal重构树的一些问题

## kruskal重构树的应用
### NOI2018
**[归程](https://www.luogu.com.cn/problem/P4768)**
**问题描述**
给定一个$$G(n, m)$$的无向图，每条边有$$(l, a)$$表示长度，海拔，一开始在`1`号点
接下来的$$q$$天，每天都会换一个新的出发点$$v$$，并且会告诉你当天的水位线$$p$$
水位线$$p$$意味着所有$$a \leqslant p$$的边，都有积水

现在从$$v$$出发，到达`1`号点，在出发点你可以有一辆车，但是车不能经过有积水的边，
如果遇到有积水的边，要停下来步行，现在要最小化步行经过的边的总长度
天和天是独立的，每一天车都会重置在出发点

**算法分析**
如果在$$u$$点下车，那么一定是沿着最短路回到点`1`（因为步行没有任何限制）
所以可以先`dijkstra`预处理从`1`开始的单源最短路`dis[1...n]`

接下来每一天给定出发点`st`，问题转化成，从$$st \to u$$要求**可达**，`chmin(ans, dis[u])`
可达的充要条件是**存在一条**$$st \to u$$的路径**没有积水**
那么存在的问题，很自然地想到 **min-max**，求出**最大生成树**，那么要求
从$$st \to u$$最大生成树的**瓶颈路 min 最小边权**$$> p$$

因为`st`一定是叶子结点，因为最大生成树，所以往祖先节点权值是**逐渐减小的**
可以考虑从`st`开始树上倍增，只要`wgt(anc) > p`就往上跳，跳到深度最小的`wgt(r) > p`的节点$$r$$
那么所有满足条件的$$u \in |r|$$，即在$$r$$的子树中，找到子树`dis`的最小值即可，子树`dis`最小也很方便求

### 思路总结
经过的边有权值限制，**只能经过权值大于$$x$$的边**，之类的问题，可以建出 kruskal 重构树
然后从`v`开始，如果满足条件就往祖先上跳，跳到深度最小的，不能跳的点为止，这个点记为$$r$$
那么相关的问题，就转化成$$r$$的**子树的问题**

###  [ONTAK2010] Peaks
**[P7834 [ONTAK2010] Peaks 加强版](https://www.luogu.com.cn/problem/P7834)**
**问题描述**
给定$$G(n, m)$$无向图，第$$i$$个点有点权$$a_i$$，边有边权，给定`q`个询问，每组询问`(u, x, k)`
求从$$u$$开始仅仅经过权值$$\leqslant x$$的边，所能到达的权值第$$k$$大的点的权值
如果不存在，输出`-1`，需要在线

**算法分析**
权值$$\leqslant x$$，考虑**重构树的瓶颈路**，构造最小生成树的 kruskal 重构树，然后要求瓶颈路$$\leqslant x$$即可
瓶颈路即最小生成树中，边权最大的权值

在 kruskal 重构树中，找到深度最小的点$$r$$，从$$u$$开始树上倍增即可，满足条件的点，一定在$$r$$及其子树中
那么就可以考虑`dfs序`，在`[l(r), r(r)]`区间内的第`k`小，这可以用主席树来求解
特别需要说明的是，在主席树建树的时候，只插入原图上的点`([1...n])`，kruskal 重构树上的虚点不插入
虚点不插入，就是遇到虚点的时候，不要更新版本，`ver[i] = ver[i-1]`即可

另外，这个问题有可能无解，什么时候无解呢？找到祖先`r`之后，如果`r`及其子树的`sz[r] < k`，那么无解
（这里统计 size 的时候，虚点的`size = 0`）

#### 算法实现
只给出主席树建树过程的实现，这是这个问题的难点
```bash
template<typename T>
void build(const vector<T> &a, map<int, int> &ori, int N, F f) {
	int tot = 0;
	map<T, int> mp;
	assert(a.size()-1 <= (N+1)/2);

for (int i = 1; i < (int)a.size(); i++) mp[a[i]] = 0;
	for (auto &p : mp) {
		p.second = ++tot, ori[tot] = p.first;
	}

_n = tot;
	vector<Node> ((int)tot<<5, Node{}).swap(nd);
	vector<int> ((int)N+5, 0).swap(ver);

for (int i = 1; i <= N; i++) {
		auto u = rm[i];
		ver[i] = ver[i-1];
		if (u <= n) ver[i] = insert(ver[i-1], 1, _n, mp[a[u]], f);
	}
}
```
### [CERC2016] 机棚障碍 Hangar Hurdles
**[机棚障碍 Hangar Hurdles](https://www.luogu.com.cn/problem/P3684)**
**问题描述**
给定一个$$n \times n$$的网格，每个格子要么是空的，要么有障碍物，现在有一个边长是**奇数**$$k$$的集装箱
（集装箱是一个正方形，尺寸是$$k$$，包含`k`行`k`列）
定义集装箱的坐标是中心点的坐标，可以上下左右移动，但是不能碰到障碍物，也不能移出边界
给定`q`对格子$$(A_k, B_k)$$，求从$$A_k$$移动到$$B_k$$的集装箱最大尺寸

**算法分析**
对于每个点，可以先二分预处理出，以这个点为中心的，最大边长的正方形是多少？
判定的方法就是，将`#`看作`1`，如果二分出来的正方形的面积和是`0`，那么合法

接着考虑`bfs`，如果相邻两个位置的**最大正方形边长**$$k$$一样，那么并查集合并
（或者不用 bfs，直接暴力检查每个点，和它的四个邻居，看一下是否可以合并）
之后再次检查每个位置$$A$$，以及它的 4 个**邻居**$$B$$，如果$$(A, B)$$不在一个连通块内
（不属于一个并查集），那么取它们最小的$$k$$作为边长，$$k = \min(k_A, k_B)$$
加入边$$(A, B, k)$$

那么对于该问题，实际上就是求$$A_k \to B_k$$的所有路径中，能通过的最大尺寸
首先我们要让路径上的边尽可能大，**能通过**的限制，取决于找这些边中的**最小边权**
这实际上就是**最大生成树的瓶颈路**，用`kruskal`重构树，找`LCA`即可解决

### ICPC WF Moscow Invitational Contest L
**[L. Labyrinth](https://codeforces.com/problemset/problem/1578/L)**
**问题描述**
给定一个$$(n, m)$$的无向连通图，$$m$$条边，其中第$$i$$条边是$$w_i$$宽
每个房间有一个糖果，吃下后会越变越宽，吃下房间$$i$$的糖果后，宽度会$$+c_i$$
不一定要在第一次去这个房间的时候吃糖，但是每颗糖只能吃一次
在图中行走的时候，你的宽度必须$$\leqslant$$通道的宽度，现在你在`1`号房间开始旅程
你可以调整你的起始宽度，希望吃掉所有的糖果，问这是否可以做得到？
如果可以，求出最大起始宽度

**算法分析**
不难发现，要吃掉所有的糖果，那么合法路径一定在**最大生成树上**，遍历生成树即吃掉所有的糖果

那么怎么吃呢？假设当前重构树的节点（虚点，表示边权）是$$U$$
不妨设左子树是$$V_1$$，右子树是$$V_2$$，先吃完一棵子树，再吃另一棵一定不劣

> 怎么证明？
可以用反证法，要是一棵树吃一半，另一棵吃一半，再返回来把剩下的吃完，意味着你吃完$$|V_1|$$之后，还能顺利通过$$U$$
那么你不如先把$$|V_1|$$都吃干净，然后再吃兄弟子树，这样可以保证你通过$$U$$的时候，宽度尽可能小
（反正你进入兄弟$$V_2$$去吃的时候，不要再返回$$U$$了，你爱怎么吃怎么吃）

记$$dp_u$$表示在$$u$$这个点，对应的最大**起始**宽度，（起始，意味着还没有开始吃子树）
> 如果先吃$$v_1$$，再吃$$v_2$$呢？记$$sz_v$$为$$v$$及其子树$$\sum c$$的和

首先起始宽度收到$$W_u$$的限制，$$beg + sz(v_1) \leqslant W_u$$，从而$$beg \leqslant W_u - sz(v_1)$$
另外要考虑到$$dp(v_2) \to dp(u)$$的转移，你要继续吃$$|V_2|$$，那么一定受到$$dp(v_2)$$的限制
同时有$$beg + sz(v_1) \leqslant dp(v_2)$$，即$$beg \leqslant dp(v_2) - sz(v_1)$$

> 综上所述，存在转移（先吃$$v_2$$再吃$$v_1$$是完全对称的）

```math
dp(u) \leftarrow \min(W_u - sz(v_1), dp(v_2) - sz(v1)) \\
dp(u) \leftarrow \min(W_u - sz(v_2), dp(v_1) - sz(v2))
```
其中$$dp(u)$$是上述二者取一个$$\max$$，$$dp(root)$$就是答案，$$dp$$值出现负数的时候是无解的

具体实现的时候，用**记忆化 + 树形dp**，对于叶子结点`u`，令`mx = *max_element(wgt.begin(), wgt.end())`
叶子结点$$dp(u) = mx$$

### Codeforces Round 673 (Div. 1)
**[D. Graph and Queries](https://codeforces.com/contest/1416/problem/D)**
给定一个$$(n, m)$$的无向图，每个点上的权值构成一个`[1...n]`的排列，第$$i$$个点权值是$$p_i$$
然后`q`个询问，每个询问有如下形式
`1 v`，所有$$v$$可达的顶点$$u$$（包括$$v$$本身），找到$$p_u$$最大的$$u$$，输出$$p_u$$并且令$$p_u = 0$$

`2 i`，删除第$$i$$条边

注意第一种操作，有可能$$v$$能到达的所有$$u$$，对应的$$p_u = 0$$，这个时候随便选一个$$u$$是不会影响任何事情的
可以选择任意一个$$v$$可达的$$u$$，并且输出`0`

**算法分析**
> 只看操作`1`怎么做

实际上，就是令$$v$$为**根**，考虑$$v$$的子树，那么就是`dfs序`中`[l(v)...r(v)]`，区间查询最大值
单点修改`l(u) -> 0`，这可以用线段树解决

> 删边怎么处理？

不好做我们就离线，考虑时间戳，记一下每一条边的死亡时间$$t, \ e_i = (u, v, t)$$
那么对于每次的询问，实际上我们就是从`u`点开始，往上尽量去跳
如果询问`1`的时间戳是$$T$$，我们要从`u`沿着$$t_i \geqslant T$$的边，往上跳到最浅的$$r$$
对$$r$$执行线段树查询

这里就可以考虑** kruskal 重构树了**，边权定义为时间戳，求出**最大生成树**，对于$$> n$$的虚点$$r$$
我们有$$W(r) = t$$，同时令虚点的$$p(r) = 0$$，不会对结果产生影响
从`u`开始树上倍增往上跳，如果$$W_r \geqslant T$$就跳，跳到最浅的$$r$$，对`[l(r)...r(r)]`单点修改，区间查询即可

> 算法实现的坑点

图可能不连通，这个时候需要检查
```bash
for (int i = 1; i <= N; i++) {
	if (dsu.find(i) == i) {
		i 作为并查集的根的时候，执行
		dfs(dfs, i, 0);
	}
}
```

### Codeforces Round 767 (Div. 1)
**[E. Groceries in Meteor Town](https://codeforces.com/contest/1628/problem/E)**
**问题描述**
给定$$n$$个点的无向连通图，每条道路有一个危险值$$w_i$$，每个点都有一个杂货店，但最开始所有杂货店都关闭
我们只关心开着的杂货店，你有`q`个查询
类型1，将编号`[l...r]`的杂货店开启（已经开启则忽略）
类型2，将编号`[l...r]`的杂货店关闭（已经关闭则忽略）
类型3，查询从建筑`x`到**任意开启的商店**的简单路径上的最大危险值，无路径输出`-1`

**算法分析**
从给定节点，到任意节点，任意简单路径的最大/最小值问题，不难想到用 kruskal 重构树来解决
假如指定开启的商店是$$y$$，$$(x, y)$$简单路径的最大危险值，只要求最大生成树，然后求$$W(lca)$$即可

> 静态版本比较好做

只需要$$x$$倍增往上跳，跳到第一个$$?$$，满足$$\exists v \in |?|$$，$$?$$的子树存在点$$v$$
使得$$v$$是开启的，即$$v$$的权值（状态）是`1`

类型 1 2 操作，$$v$$的开启关闭状态，对应$$?$$的`dfs`序，子树的区间查询，区间修改
（只要子树的区间和`> 0`，就意味着存在一个点是开启状态）

> 但是，题中的修改，并不是连续的一段，怎么办？我们处理`[l, r]`的区间修改，只能是原址考虑
考虑在原节点编号`[1...n]`上线段树维护

对于点$$x$$，找到状态是`1`的点的点集$$|Y|$$，那么所有可能的最大危险值
```bash
x and
{y1, lca1} -> w(lca1)
{y2, lca2} -> w(lca2)
{y3, lca3} -> w(lca3)
......
......
{ym, lcam} -> w(lcam)
```
注意到，问题给出的就是一棵树，那么树的最小生成树当然还是这棵树本身
于是$$(x, y)$$简单路径的最大危险值，对应**最小生成树的瓶颈路**，也就是$$W(lca)$$

要使得到所有状态为`1`的点的**瓶颈路尽可能大**，那么要找到`LCA`最浅的点
实际上呢？就是找点集$$|Y|$$的`LCA`，这可以转化成`dfs 序的 dfn 值`的$$\min, \max$$问题

> 维护 dfn 来求点集的 LCA

如果状态从`1`变成`0`，关闭商店，那么就令$$\min = +\infty, \max = -\infty$$
这样这些点的`min, max`值，都不会对答案产生影响
我们就可以关注整个区间`[1...n]`的**区间查询最值**

**点集的`LCA`**
实际上就是点集中`dfs 序中 dfn`最大的点和最小的点，它们之间的`LCA`
（具体的证明，可以考虑`dfs 序`求`LCA`，实际上就是找`dfn`最小的点）

那么具体做法就很简单了，用线段树维护`dfn`数组，然后找到最小和最大的`dfn 值`
分别是`min-dfn, max-dfn`，这两个值对应的就是`dfn`最小和最大具体是多少？
再对应到树中原先的节点，就分别是`u = rm[ mn ], v = rm[ mx ]`，然后求出`u, v`的`LCA`
对应的$$W(lca)$$就是答案

线段树维护区间`dfn`的`min, max`，操作1 2则对应区间修改

> 总结

这题的核心，在于说题中给定的是**一棵树**，那么两点之间的路径是**唯一的**
并且路径的最高点，就在`LCA`处，使得`LCA`处取得最大的权值，就要构建 kruskal 最小生成树的重构树

对于合法的点集$$Y$$，可能的最优解，一定都在和每一个$$y_i$$的`LCA`处取到，那我们就找这些`LCA`中
**“最 LCA 的点”**，也就是`LCA`最浅的点，即点集的`totlca`，那么瓶颈路就是`LCA(x, totlca)`

#### 算法实现
给出**难点，线段树的 lazy 标记的设计**
大体来说，线段树维护`minv, maxv`表示真正的值，`showmn, showmx`表示展示的值
执行操作 2 的时候，令`sgn = 0`，展示的值`showmn = INF, showmx = -INF`
表示说具体的值不展示，最后我们求的是整个区间的`showmn, showmx`

```bash
struct S {
    int minv, maxv;
    int sgn, showmn, showmx;
};

S op(S a, S b) {
    S res;

res.minv = min(a.minv, b.minv);
    res.maxv = max(a.maxv, b.maxv);

int sta = a.sgn + b.sgn;

res.sgn = (a.sgn & b.sgn);

if (res.sgn == 1) {
        res.showmn = res.minv;
        res.showmx = res.maxv;
        return res;
    }

res.showmn = min(a.showmn, b.showmn);
    res.showmx = max(a.showmx, b.showmx);

return res;
}

S mapping(int f, S x) {
    S res = x;
    res.sgn = f;

if (res.sgn == 0) {
        res.showmn = INF;
        res.showmx = -INF;
    }
    else {
        res.showmn = res.minv;
        res.showmx = res.maxv;
    }

return res;
}

int comp(int f, int g) {
    return f;
}

int id() {
    return -1;
}
```

### AGC002 D - Stamp Rally
**[D - Stamp Rally](https://atcoder.jp/contests/agc002/tasks/agc002_d)**
**问题描述**
给定$$(n, m)$$的无向连通图，有$$Q$$组活动，每组活动的规则如下

- 一个人从$$x_i$$出发，另一个人从$$y_i$$出发

- 总共必须访问$$z_i$$个顶点，重复访问的不计（只要其中一个人访问过一个顶点，这个顶点后续就不计）

- 得分是两个人经过的边中，编号的最大值，目标是使得得分最小化

**算法分析**
没有总共必须访问$$z_i$$个顶点的限制，答案就是$$(x_i, y_i)$$在**最小生成树的重构树**上的`LCA`
可以考虑**二分答案**，二分一个最大编号$$k$$，$$x_i, y_i$$分别沿着$$\leqslant k$$的**祖先**尽量往上跳
假设说跳到了$$s_1, s_2$$，考虑以下情况

如果$$s_1 \neq s_2$$，那么它们跳到的祖先并不在一个连通块内，它们经过的点有多少个呢？
**经过的点的个数恰好为子树叶子的个数**，答案是$$tot = |s_1| + |s_2|$$

如果$$s_1 = s_2$$，那么它们跳到的祖先在一个连通块内，直接是$$tot = |s_1|$$

如果$$tot = z_i$$恰好成立，说明跳的是一个合法的位置，这样尽可能往上跳到最浅的位置即可

### Grakn Forces 2020 G
**[G. Clusterization Counting](https://codeforces.com/contest/1408/problem/G)**
**问题描述**
给定$$n$$台计算机，编号从`[1...n]`，给定边权$$a(i, j) \in [0, \dfrac{n(n-1)}{2}]$$，并且边权是一个排列
你要将计算机分成$$k$$个集合$$A_1, A_2, \cdots, A_k$$，使得满足
每台计算机恰好在一个集合$$A_j$$中
对于任意两对计算机$$(s,f), (x, y)$$，如果$$s, f, x$$来自同一个集合，必须满足$$a(s, f) < a(x, y)$$
求分组的方案数
其中`n`比较小，在$$1 \leqslant n \leqslant 1500$$

**算法分析**
不难发现，如果$$x \in X, y \in Y$$**不在一个集合**，考虑并查集，合并$$(x, y)$$
对于边$$a(x, y)$$，只要保证按照**最小生成树的 kruskal 重构树**的顺序来合并
就可以保证$$\forall a(s, f) < a(x, y)$$

并且还发现，一个组$$A_u$$实际上就是$$u$$及其子树**叶子结点的集合**

另外，这里还要保证，`each (s, f)`，那么就意味着$$x$$及其子树，必须形成一个团
这个只要判断`szEdges(u) = (sz(u) - 1) * sz(u) / 2`是否成立即可，其中`szEdges(u)`表示虚点（即边）的数量

那么我们可以先`dfs`打表一下，预处理出哪些点`u`的子树是满足条件的

> 接下来怎么求方案数呢？

考虑`dp`，只不过我们这里按照`dfs 序`来进行 dp，考虑`dfs 序`的时候，虚点我们并不计入，即`虚点的 l(u) 不会 ++idx`
（取而代之，我们可以让虚点的`l(u) = n+1`）

然后呢？对于满足条件的点，它对应`dfs 序`上连续的一段$$[l_u, r_u]$$，我们把所有满足条件的点$$u$$
根据`dfs 序`处理出满足的区间$$[l_u, r_u]$$，并且把$$l_u$$**挂载到**右端点$$r_u$$上

问题转化成，从若干个合法的区间中，选出$$k$$个不相交区间，使其恰好覆盖$$n$$个点`[1...n]`的方案数

选出$$k$$个，可以背包，$$dp(i, k)$$表示当前右端点是$$i$$，已经选了$$k$$个的方案数
枚举左端点$$j \in |i|$$，$$dp(i, k) \xleftarrow{+=} dp(j-1, k-1)$$

最后的答案呢？$$dp(n, k)$$就是答案

> 坑点，每一个叶子结点（对应原图上的每一个点），单独为一个集合，这样的方案也是可行的
所以对于每一个$$u \leqslant n$$的点，`ok(u) = 1, vec[ r(u) ].push_back(l(u))`

## ICPC 2021 上海 H
**[Life is a Game](https://ac.nowcoder.com/acm/problem/231127)**
**问题描述**
给定$$(n, m)$$无向图，一开始你在$$x$$号点，并且有$$k$$的能力值，如果你在$$i$$号点
同时还可以获取$$a_i$$的能力值，一个点的能力值只能被获取一次
你需要能力值$$\geqslant w_i$$才能通过边$$i$$，现在给你$$q$$个询问，每个询问都形如$$(x, k)$$
一开始时候你没有获取任何能力值，只有初始能力$$k$$，对每个询问给出回答，你最后能获得的最大能力值是多少

**算法分析**
显然按照边权从小到大排序，边权越小的越容易通过，构造最小生成树的 kruskal 重构树
对于每个询问，从$$x$$点开始往上跳，进行树上倍增

假设当前的点是`u`，要跳的点是`to`，初始能力是`K`，子树的$$sz(u) = \sum a_i, i \in |U|$$
`u`能跳到`to`，当且仅当$$sz(u) + K \geqslant wgt(to)$$，就这样找到**第一个不满足**的点$$r$$
那么$$r$$的`sz(r) + K`就是答案

**树上倍增的实现**
```bash
auto check = [&](int x, const int K) -> int {
	int res = K + sz[x];
	while (x && x != tot) {
		int t = x;
		for (int i = LOG; i >= 0; i--) {
			int to = go[x][i];
			if (to == 0) continue;

if (wgt[to] <= res) x = to;
		}
		// 如果 x 不能再往上抬了，就 break
		if (x == t) break;
		res = K + sz[x];
	}
	return res;
};
```

看完文章有啥想法

算法小站

wiki 主题

图论

kruskal重构树的一些问题

目录