Description：

给一棵树，每个点有权值，多次询问某个子树中出现过恰好 $k$ 次的权值的个数。

$1\leqslant n\leqslant 10^5$

Solution1：

显然可以树上启发式合并。 $O(n\log n)$

Solution2：

首先求出树的 $dfs$ 序问题就变成了求区间出现过恰好 $k$ 次的数的个数，显然可以莫队。 $O(n\sqrt n)$

Solution3：

我们把询问离线按右端点排序，然后维护每一个左端点的答案，那么我们可以发现只有这个权值出现的 $k$ 次之前的答案会改变，于是我们可以用一个树状数组维护左端点的答案，对每个权值维护一个指针表示 $k$ 次前出现的位置，然后每次这个指针到他下一次出现的位置的答案会改变，于是区间加和单点求值即可。

Solution4：

有一个值域分块 $+$ 序列分块的做法，可以解决序列出现 $k$ 次的权值的个数问题，首先把值域分块，对于出现次数 $>\sqrt v$ 的数最多有 $\sqrt v$ 个，这个可以每个权值维护一个 $vector$ 查询区间出现次数，对于其他的数，我们可以求出从开始到每个块结尾的出现次数，以及从第 $i$ 个块到第 $j$ 个块出现次数为 $k$ 的数字个数，然后询问的时候暴力扫两边的小块，同时根据大块中的出现次数加减答案，最后用一个栈撤销即可。

$O(n\sqrt{n\log n})$