考虑对于每一个深度为 \(i\) 的询问，答案为所有 [\(dep = i\) 的结点的子树合并起来，子树合并时被删除的结点个数] 的和减去 \(dep = i\) 有儿子的结点数。
直接暴力 \(trie\) 合并即可。显然时间复杂度 \(\le \sum\limits_{u=1}^{n} siz_{u的轻儿子}\)
ac link
考虑建立一个中转点，以 \(n \equiv 0 \pmod 2\) 为例。
这个中转点为 ：
UUUUU
DDDDD
UUUUU
DDDDD
考虑遇到一个不符合答案的情况。遇到：
LR..
LR..
......
就直接旋转即可。
否则会遇到这种情况：
LR..
U....
D....
那么我们的人物是把那个
U.....
D.....
转成 LR....。
于是就转化成了一个子问题。递归解决即可。
待填坑
原文：https://www.cnblogs.com/zkyJuruo/p/14263693.html