P9352 题解

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,a_v)\)。那么顺着枚举 \(u\) 就是正确的。\(pos_u\) 就是并查集了，直接做就可以了！

代码，时间复杂度 \(O(n\log n)\)。