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)\)。
标签:子树,题解,pos,P9352,枚举,DP,dp From: https://www.cnblogs.com/liangbowen/p/17571984.html