[CSP-S 2023] 种树

对于方案难以通过贪心或 DP 直接构造的题目，可以尝试二分答案后贪心或 DP。

以及这道题要求所有树长成时间的最大值最小，提示我们二分答案。

对于每个节点，给定它长成的最后期限后，可以计算出种下它的最后期限。

至于父亲种下时间 $t_u$ 必须早于儿子种下时间 $t_v$ 的限制，我们令

$$\displaylines{t'_u=\min\{t_u,\min_v t_v-1\} }$$

以 $t'_u$ 为修正后的种植最后期限，忽略祖先关系之间的限制，如果能够构造出任意一组合法方案，那么不断交换所有不满足限制的父亲和儿子，一定在有限步内结束，构造出一组满足限制的方案。

判断是否存在一组忽略祖先关系限制后的方案，只需按照 $t_u'$ 从小到大排序，贪心选取即可。