题解：AT_kupc2021_e PERMST

KidA · 2026-08-16 11:49:35 · 题解

提供一种树剖的实现。

乍一看这题似乎不可做，此时我们应当考虑提炼模型。

仔细观察，直觉告诉我们蓝边和红边之间存在约束关系。

具体的，对于一条蓝边，它不会成为最小生成树的树边且最小生成树唯一，当且仅当其两个端点路径上的红边边权严格小于其边权。

这似乎已经形成了一种约束条件，我们称这种关系为覆盖。有了约束，我们就能建图。若蓝边 i“覆盖”了红边 j，则考虑连一条由 j 指向 i 的边。

现在回到题目所求。题目希望我们找到一个赋权值的方法，使所有的“覆盖”都被满足，且字典序最小。

我们一个一个来解决：

• 为了满足所有的覆盖，我们显然可以让蓝边赋更大的权值。在蓝边赋上权值后，那些被这条蓝边“覆盖”的红边相当于失去了约束（因为更大的权值已经被蓝边抢走了），所以它们也可以参与竞争大的权值，以便给尚有约束的边提供更小的权值。

• 由于要求字典序最小，我们可以在相同条件下先给编号大的边分配。

根据上述思考，我们已经可以总结出分配权值的算法流程：

• 维护一个大根堆，保存候选边的编号。
• 倒序枚举权值，取出大根堆堆顶，将权值分配给它。
• 对于蓝边，将它端点路径上的红边约束全部去除。
• 寻找那些已经没有约束的红边，将其加入候选堆中。

这样直接做是 O(M^2 \log M) 的（N,M 同阶），无法通过，考虑数据结构优化之。

我们想起了我们一开始建立的图论模型，容易发现去除约束相当于图中红边的出度减一。而我们需要对一条路径上的所有红边都执行这一操作，不难想到使用重链剖分维护。

对于寻找候选红边，我们发现直接找是 O(M) 的，可以利用线段树维护区间内红边出度的最小值，然后进行单点修改，但区间内最小值大于 0 的就进行剪枝，每找到一条红边入堆下次就不再找它（这个可以设其最小值为正无穷来解决）。由于红边数量最多 n-1 条，因此时间复杂度可以接受。

实现有一定难度，因此给出代码。

综上所述，本题考查了对最小生成树的深层理解，对于图论建模、数据结构优化的能力有较高要求，是一道不可多得的好题。