可离线处理子树相关信息统计的算法，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

首先发现对每棵子树进行信息统计时，只需要合并所有儿子节点所在子树信息，最后加上该节点本身信息即可。

考虑信息合并的过程，类比并查集的启发式合并，发现把节点数少的子树信息合并到节点数多的子树将得到更优复杂度。

于是考虑保留重儿子子树的统计信息，然后暴力遍历轻儿子子树，合并结果。

具体实现为先 $\text{dfs}$ 处理轻儿子子树的询问，再删除轻儿子子树的统计信息(否则空间复杂度难以承受)。

然后处理重儿子子树的询问，但保留重儿子子树的统计信息，最后再次遍历轻儿子子树，然后把信息暴力合并。

关于时间复杂度，发现某个节点每被额外统计一次当且仅当他每有一个祖先节点为轻儿子。

由于每个节点到根节点最多有 $O(\log n)$ 条轻边，于是每个节点最多被统计 $O(\log n)$ 次，于是总时间复杂度为 $O(n\log n)$。

CF570D

给定一个以 $1$ 为根的 $n$ 个节点的树，每个点上有一个小写英文字母。每个点的深度定义为该节点到 $1$ 号节点路径上的点数。

每次询问 $a,b$，查询以 $a$ 为根的子树内深度为 $b$ 的节点上的字母重新排列之后是否能构成回文串。