\(O(n\log^2n)\) 做法：邻域维护除父亲和重儿子之外的树的数据结构，问题变成 \(n\log n\) 次插入与 \(n\) 次查询第 \(k\) 小。
\(O(\frac {n\log^2 n} {\log \log n})\) 做法：两种做法，可以把前边的问题用 \(k\) 叉树做， 取 \(k=\log \log n\) 即可，也可以将邻域内改成不维护前 \(k\) 大的儿子，取 \(k=\frac {\log n} {\log\log n}\)，这样也是对的。
引入多树二分问题，我们有 \(m\) 个集合 \(T_i\)，要支持动态加删，查询所有集合中的第 \(k\) 大/小，这个问题是能做到 \(O(\sum \log|T_i|)\) 的。
一个点儿子从大到排序后，我们记第 \(1\) 个为 \(0-\)轻儿子，接下来 \(2\) 个 为 \(1-\)轻儿子，接着 \(4\) 个是 \(2-\)轻儿子，接着 \(2^{2^{i-1}}\) 个为 \(i-\)轻儿子，这样一组组划分。
我们对于每组内开平衡树一起维护，我们记为 \(T_i\)，对于一个点 \(u\)，\(\sum \log|T_i|=O(\log deg_u)\)，对于修改一条链，不难发现假如我们经过一个 \(i-\)轻儿子的轻边，\(siz\) 会至少变成 \(2^i\) 倍，在 \(T_i\) 这颗平衡树中修改复杂度是 \(O(i)\)。
于是对于单次修改，我们的复杂度降至 \(O(\log n)\)，对于查询，我们相当于是做一次多树二分，而 \(\sum \log|T_i|=O(\log deg_u)=O(\log n)\)，总复杂度 \(O(m\log n)\)。