CF2033G Sakurako and Chefir 笔记

如果没有向上的步数限制，就是经典的换根 DP 问题。

考虑向上步数限制，同理用换根 DP 思路，要么直接向下走，这一部分可以预处理；要么向上走，再走进父亲的最深的儿子，那么这就是一个在自己和自己 $k$ 级祖先之间的一个取 $max$ 操作。

这个操作可以使用倍增或者树链剖分维护，当预处理向上走一步 $f_{u,0}$ 时，若 $\mathrm{fa}(u)$ 的最深儿子是 $u$，则同换根 DP 要取第二深的。

时空复杂度 $O(n\log n)$。