OU 瑞平：你这玩意跟我那个做法感觉没啥区别啊，唯一的区别可能是，常数变大了

写这篇题解的人真是太不牛了。

考虑对原树进行 Top Cluster 分块，这可以将原树的边集不重不漏划分为 $\mathcal O(\sqrt{n})$ 个大小为 $\mathcal O(\sqrt{n})$ 的块。我们先求出 LCA 为 $u$ 的所有答案，然后做树上前缀和即可。

对于单点 $u$，考虑引起贡献的两个点。如果 $u$ 不是这棵簇的界路径上的点，那么引起贡献的 $x, y$ 均与 $u$ 在同一棵簇内，可以直接 $\mathcal O(\left(\sqrt{n}\right)^3)$ 复杂度内暴力解决。

否则，下面的所有点 $u$ 都在某棵簇的界路径上。我们考虑这样的问题：对于当前节点 $u$，有一个数组 $f$，其中 $f_S$ 表示满足 $v \in \textrm{Subtree}(u)$，且 $u \sim v$ 路径上的所有出现过点权集合为 $S$ 的种类数。如果给出 $f$，且仅统计所有 $v \in \textrm{Subtree}(u)$ 的贡献，那么答案是

我们可以换一个角度理解这个事情，假设我们在做 FWT，那么我们在 $f$ 每一维做一个神秘的线性变换到 $g$：$g_0 \gets f_0 + a_uf_1, g_1 \gets a_u(f_0 + f_1)$。答案是 $f_0$。这同样可以 $\mathcal O(k \cdot 2^k)$ 计算答案。

我们假设这棵簇真的就长得像一条链，那么每次 $f$ 向上的时候只需要把所有 $c_x \not\in S$ 的 $f$ 值加到 $f_{S \cup \{c_x\}}$ 里，并且对原 $f_S$ 清零。即可。这条链的长度是 $\mathcal O(\sqrt{n})$ 的，但是有意义的合并只会发生 $k$ 次，而 $2^k + 2^{k-1} + \dots + 1 = \mathcal O(2^k)$，所以复杂度依旧是 $\mathcal O(k \cdot 2^k)$。

现在这棵簇长得不像一条链了！但是在 $u$，我们可以枚举所有簇内的 $x$（其实是包括 $u$ 的）满足 $x$ 的最近簇路径节点为 $u$，这时我们再枚举簇外节点 $y$ 即可补全贡献。所有 $y$ 的信息被携带在数组 $h$ 里，我们只要让 $T$ 表示 $u$ 到 $x$ 路径上所有出现颜色集合，那么 $h_T$ 事实上就是所有可能 $y$ 和 $x$ 的路径答案之和。只要计算出 $h$，贡献是容易简单统计的。

最后，答案唯一可能出现问题的是所有的簇界点，因为它可能同时是若干个簇的上界点，我们在 FWT 暴力合并不同簇的 $f$ 数组时加入贡献即可。

时间复杂度即为 $\mathcal O(n\sqrt{n} + k2^k\sqrt{n})$。