题解：P6122 [NEERC 2016] Mole Tunnels

Priestess_SLG · 2025-08-18 20:28:22 · 题解

比较经典的 Regret Greedy。前置知识 GSS9 trick：选中一条边之后将这条边的边权取反，下一次被选中的时候边权就可以直接抵消。

先考虑一个错误的做法：每一次每一只鼹鼠贪心的前往这个距离最近的点，容易想到树形 dp 维护：设 f_i 表示 i 子树内前往一个能前往的点的最小距离，那么更新一个结点状态之后可以跳父亲结点更新所有的 f_i 值，查询距一个点 i 的最近可以前往点距离同样可以暴力跳父亲结点然后更新答案，因为树是二叉树，树高为 \log n，所以时间复杂度有保障。

但是这显然是错的，因此考虑 Regret Greedy。考虑到若有一条边被不同方向经过了两次，那么不如交换路径然后不经过这条边优秀。此时考虑套用 GSS9 trick，记录每一条边从父亲往儿子结点走的路径数减去从儿子往父亲结点走的路径数：

• 若路径数差 \ge 0，则将儿子往父亲边权取反，另一方向边权不变。
• 若路径树差 \le 0，则将父亲往儿子边权取反，另一方向边权不变。

这个差值显然可以简单更新，f 数组内 dp 值的算法也是简单的，同时可以在更新 f 数组的同时记录 g 数组表示 f 中对应的那个点，模拟上述流程，总时间复杂度为 O(n\log n) 可以通过。

代码，因为没有封装更新过程所以有点长。