【模板】虚树

配合 O(nlogn)-O(1) 即可轻松通过。

考虑用启发式合并，用 map 直接维护每一个子树 $u$ 内每一个颜色 $c$ 的 $cnt_{u,c},s_{u,c}$，分别表示 $u$ 子树内颜色为 $c$ 的点数和点的深度之和。

考虑合并 $u$ 和其子节点 $v$ 对答案的贡献（此时 $v$ 还没有合并到 $u$ 上），那么对于一种颜色 $c$ 增加的答案就是 $cnt_{u,c}\times s_{v,c}+s_{u,c}\times cnt_{v,c}-2\times cnt_{u,c}\times cnt_{v,c}\times dep_{u}$，其中 $dep_u$ 为 $u$ 的深度。

解释一下这个式子：前面两个积算出所有颜色为 $c$ 的点到根节点的距离之和，然后减去多余的部分（这里就是 $u,v$ 的 LCA）。