自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 22:47:35，当前版本为作者最后更新于2023-07-21 17:13:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

problem & blog。

HerryHuang 的 DP 专题中最喜欢的一题，抢第一篇题解 /fendou。

关于题意：只有往猫那里扔路障，猫才会动，否则只会原地坐牢。猫如果要走动，是一下子走到最高点，而不是慢慢挪动。

假设猫在 $u$ 点。现在往 $u$ 扔路障，猫会跑去最高点，然后他无法返回到 $u$ 的其他子树了，因为 $u$ 被堵上了。

实际上，每次只给猫留一条活路，猫的行动点就是固定的。那么只需找到子树中能移动的次数最大的子树，然后过去即可。

显然可以 DP。设 $dp_u$ 表示以 $u$ 为根的子树中，猫在 $u$ 点，可以走的最长距离。令子树中点权最大的点是 $pos_u$，那么 $dp_u=\max\{dp_{pos_v}+\operatorname{dist}(u,v)\}$。

但有一个潜在条件是 $a_u>a_{pos_v}$，而 DP 又要先枚举小的 $a_u$，再枚举大的。这意味着 DP 顺序会跳来跳去，直接失去了正确性。

考虑连边 $(a_u,a_v)$。那么顺着枚举 $u=1\sim n$ 就是正确的。$pos_u$ 相当于找一个遍历过的最大的 $v$，上并查集即可，具体看代码。

代码，时间复杂度 $O(n\log n)$。记得开 long long。