这题场上正着想了 3h+,发现需要用大 DS,果断弃疗了。
但是如果反着做会很好做。
首先你考虑到题目要求的限制本质上是什么,一个结点只能选完其所有祖先才能选这个点,但是我们发现这个限制过于强了,我们决定同时选。
同时选就是将每个结点向父亲结点合并,这样子一定是由祖先到叶子依次合并,依然满足条件。
考虑到两个连通块的合并,就是看 \(1\) 的个数和 \(0\) 的个数的比值,具体来说可以考虑 exchange argument,就很简单了。
然后每次选比值最小的合并到父亲结点处。
感觉这种题主要是要换方向,比如正着做换成同时做。