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

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

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

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

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

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

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

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