P9352 题解

liangbowen · 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。