假设 $n,q$ 同阶。

$x$ 在路径上的出现次数可简单求出，故考虑进一步的问题查询路径上出现次数大于 $k$ 的颜色数。

首先根号分治。

整棵树内出现次数大于 $\sqrt n$ 的颜色一定不超过 $\sqrt n$ 种，对这些颜色暴力预处理出每个点的到根链上出现次数即可，查询的时候直接枚举判断。

对于其余颜色，我们考虑求出路径上出现次数等于 $i$ 的颜色个数 $c_i$，那么对答案的贡献是 $\sum_{i=k+1}^{\sqrt n} c_i$。

在树上随机撒点分块，预处理出任意两个关键点 $u,v$ 之间的路径上出现恰 $i$ 次的颜色数 $c_{u,v,i}$。对于询问 $x,y$，找到两点各自的第一个关键点祖先 $a,b$，若 $a=b$ 则直接跑暴力，否则路径 $(x,y)$ 是路径 $(a,b)$ 再加上和删除 $O(\sqrt n )$ 个点，加删点对 $c$ 的贡献我们再维护一个 $f_{u,i}$ 表示关键点 $u$ 到根链上 $i$ 的出现次数即可。

复杂度 $O(n^{1.5})$。