题意可以理解为找到一条 $1$ 到 $n$ 的路径,使得其中 $a$ 的最大值和 $b$ 的最大值之和最小。

我们可以先按照 $a$ 的值排序,然后使用 LCT 维护关于 $b$ 的最小生成树;算法的正确性很容易证明:对于每一个 $a$ 的最大值我们都取到了 $b$ 的最大值的最小值。

维护动态最小生成树:对于新加的边 $(u, v)$ ,如果已经连接,则需要断掉其中最大的一条(当前的 $b$ 值比最大的 $b$ 值还大就不用加了),否则无脑 link 。所以我们的 LCT 还要存储下最大的边以及对应的编号。

由于 LCT 只能维护点不能维护边,我们可以考虑化边为点,总共有 $n$ 个 LCT 中的点表示实际意义的点,以及 $m$ 的 LCT 中的点表示实际意义的边。这样子瞎搞即可。

注意一定要当 $1$ 和 $n$ 已经联通时才能用当前的状态尝试更新答案哦!

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×