CF1935F Andrey's Tree

Alex_Wei · 2024-03-11 09:40:39 · 题解

CF1935F Andrey's Tree

给一个简单的线性做法。

先考虑答案下界，显然不小于 deg_v - 1，是否能达到该下界呢？

考虑 v = 1 或 v = n 的情况，此时所有编号构成连续段。对此有一个非常经典的构造：求出每个连通块的编号最大值 mx，若 mx 不是编号最大的点，则从 mx 向 mx + 1 连边。这样会连出一棵有根树，根为 mx_i 最大的连通块，且从每个连通块开始不断跳父亲都会跳到该连通块，因为每个非 mx 最大的点都有父亲，且父亲 mx 大于其 mx。

对于 v\neq 1, n 的情况，可类似构造。具体地，若不存在 mx_i + 1 = v，则使用上述方法构造即可。若存在，则还需分两种情况讨论：

• 若一部分连通块构成了 1\sim v - 1，另一部分连通块构成了 v + 1\sim n，则无论如何，连接分别属于这两部分的连通块的边的权值不小于 2，而这样的边至少有一条，所以答案下界为 deg_v。使用上述方法构造，并将 (v - 1, v) 改成 (v - 1, v + 1) 即可。

• 若并非上述情况，则存在连通块同时含有 [1, v - 1] 和 [v + 1, n] 中的点。这些连通块就是沟通 [1, v - 1] 和 [v + 1, n] 的桥梁。我们将连通块按照 mx 是否小于 v 分为两部分 L, R。对于 R 的所有连通块，从 mx 向 mx + 1 连边。对于 L，就相反地考虑，从 mn 向 mn - 1 连边。这样至少连出了 deg_v - 2 条边，因为不能连 (n, n + 1) 和 (1, 0)。

  首先要证明这样不会连出环：从 R 中的连通块出发，不断跳出边，最终一定能到达 mx = n 的连通块；从 L 中的连通块出发，要么跳到某个 R 中的连通块再跳到 mx = n 的连通块，要么跳到 L 中 mn = 1 的连通块。

  无论是从连边方式，还是从上述证明，都可以看出此时不连通（只连了 deg_v - 2 条边）当且仅当 mn = 1 的连通块属于 L。此时只需取出 R 中 mn 最小的连通块，然后在 mn 和 mn - 1 之间连边即可：容易证明此时 mn 和 mn - 1 不连通。

换根 DP 计算每个点的每棵子树的 mn 和 mx，时间复杂度 \mathcal{O}(n)。代码。