P12382

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

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

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

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

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

实现。