Colorful Tree

题目链接： HDU 2017 Colorful Tree 。

题目描述：

有 $n$ 个点的树，每个点有一个颜色 $a_i$ ，求所有 $(u,v)$ 满足 $1\le u<v\le n$ 的点对的路径上的不同颜色的和。

$n\le 2\times10^5,1\le a_i\le n$ 。

考虑对于枚举每一个颜色并计算它带来的贡献。对于枚举的颜色 $c$ ，我们应该视所有 $a_i=c$ 的 $i$ 为关键点，那么这个颜色 $c$ 的贡献就是所有经过了关键点的路径。

这个并不好算，我们考虑把它容斥为不经过任意一个关键点的路径。

此时问题就明了了：将所有的关键点去掉后的连通块的大小的平方和。

由于有关键点，我们对所有的关键点建立虚树。为了方便强行钦定 $0$ 为根，连边 $(0,1)$ ，并设 $0$ 为关键点。

接下来就我们不妨自下而上考虑：对于一个关键点 $u$ ，遍历它在原树上的儿子 $v$ ，并计算 $v$ 的子树权值和（即去掉 $u$ 之后的 $v$ 这一个连通块大小）的平方，然后将 $u$ 整个子树的权值全部置为 $0$ 。初始时所有节点均置为 $1$ 。

复杂度容易说明：建立虚树的复杂度 $\mathcal{O}(n\log n)$ ，之后每一个节点都只会出现在一个虚树中并遍历一次它的儿子，执行一遍线段树操作，于是这部分复杂度 $\mathcal{O}(n\log n)$ 。总复杂度就是 $\mathcal{O}(n\log n)$ ，可以通过。

代码十分简单，不放了。

PS: 这里虚树的作用其实是为了保证自下而上的遍历，所以也可以不用虚树，改为将所有的关键点按深度排序处理。