构造策略类题目。
首先想法很简单，从 \(1 \sim n\) 分别考虑，问题是如何决策一个点放不放。
对于一棵树，我们分为两类点：根和其它，这是因为根必然放在最后（而且选了根就可以后继无忧了），而其它点不一定，这给我的选择带来了很大的限制。
那么设当前决策到点 \(x\)，自然也是分两种情况考虑：
- \(x\) 为根。
- 若 \(x\) 所属子树内部还没有达到上界，那么先记下，等到了上界将根放进去，以后不再选这棵树的结点。
- 若 \(x\) 所属子树已经超过了上界，那么此时放入根肯定最优，不可能等到后面选一些结点再放入根。
- \(x\) 不为根。
- 若 \(x\) 所属子树还没有超过上界，那么为了最优，肯定要选择当前结点，不然后面选什么结点都挽救不回来这个结点的损失。
- 若 \(x\) 所属子树达到上界，那么需要找到一个最小的能够覆盖所有点的结点，当枚举到它时将它放入并且不再放入这棵树的结点。
注意到第四步相当于对于这棵树的一个前缀的 LCA 所属祖先链求最小值，这用数据结构是好维护的。
时间复杂度取决于自己的实现。其实你会发现根结点也没有啥很特殊的性质，只是当遇到下界的时候停止选择罢了。
字典序问题都是这种解题思路，感觉没有迷宫守卫让我惊艳。