CF1856E2
如果 \(n\le 5000\) 考虑怎么做。
首先我们对于每个节点只考虑大小关系，最后只需要从小到大标号即可。
我们考虑把答案放到 LCA 处统计。
若其只有两个儿子 \(v_1,v_2\)，那最多只有 \(siz_{v_1}\times siz_{v_2}\) 个会被统计，即令 \(v_1\) 所有数大于 \(v_2\)。
若有多个儿子，就是把儿子子树的大小分成两个集合，使得两个集合差最小。
可以用 01 背包解决。然而 \(O(n^2)\)。考虑 \(n\le 1e6\)，如何优化 01 背包？
可能有关 bitset。注意到背包所有元素的和是 \(O(n)\)。所以不同大小的个数是 \(\sqrt n\) 的。
不妨二进制拆分做 01 背包，复杂度是 \(O(\frac{1}{\omega}n\sqrt n \log n)\)。
此外，如果有一个儿子大小超过一半，是不用做背包的，这保证了复杂度。
所以树的 \(siz\) 是分一半最优，总复杂度可以用主定理计算。
实现的话，需要使用动态大小的 bitset，可以提前开好所有 \(2^k\) 大小的，用的时候用一个最合适的。
这种问题有关排列，应考虑相对顺序。再转化为背包，应想到 bitset，再观察背包的性质。