树上启发式合并是一种启发式算法，虽然算法的思路很简单以至于让人感觉没有复杂度保证，但事实上，树上启发式合并是一种时间复杂度非常优秀，适用面非常广的算法。

思想引领

首先来看一个问题：给定一棵有 $n$ 个结点的树，$q$ 次询问，每次询问结点 $x$ 的 $k$ 级后代有几个。

数据范围：$n,q\le10^5$。

树上 $k$ 级祖先/后代应该知道是什么意思吧？这里的形式化定义如下：

定义结点 $x$ 的树上 $1$ 级后代为 $x$ 的任意子结点，$x$ 的树上 $k$ 级后代为 $x$ 任意子结点的 $k-1$ 级后代。

如何解决这个问题呢？我们可以轻易地想到一个暴力的做法：对于每一个询问，DFS 到深度为「$x$ 的深度 $+k$」（在 $x$ 的基础上深度多 $k$ 的结点就是 $x$ 的 $k$ 级后代）的结点并统计个数即可。这样做的时间复杂度显然是 $\Theta(qn)$ 的，在极限情况下会超时。

那么，该怎么优化呢？