P12382

KidA · 2025-08-05 11:34:42 · 题解

比较具有启发性的树形 dp。

若按照常规的做法，按照 dfs 序转移，则第一个要求容易实现，但第二个是不好实现的。

考虑转换角度，我们不妨令 dp_i 表示节点 i 所在深度，且当前深度选的点权最大值。这样按照深度转移，则第二个要求容易实现。那么第一个呢？对于每个节点 i，它当然从上方深度的最大值转移而来。如果它前面的最大值正好是它的父节点，则选取次大值即可。

这样的时间复杂度与常规做法相同，均为 \mathcal{O}(n)。

总结：树形 dp 也可以按照层序转移。

实现。