https://www.spoj.com/problems/MTREECOL/
https://blog.csdn.net/Merry_hj/article/details/76737118
There is a tree with n nodes, each of which has a type of color represented by an integer, where the color of node i is ci.
The path between each two different nodes is unique, of which we define the value as the number of different colors appearing in it.
Calculate the sum of values of all paths on the tree that has n(n−1)2 paths in total.
Input
The input contains multiple test cases.
For each test case, the first line contains one positive integers n, indicating the number of node. (2≤n≤200000)
Next line contains n integers where the i-th integer represents ci, the color of node i. (1≤ci≤n)
Each of the next n−1 lines contains two positive integers x,y (1≤x,y≤n,x≠y), meaning an edge between node x and node y.
It is guaranteed that these edges form a tree.
Output
For each test case, output “Case #x: y” in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.
Sample Input
3
1 2 1
1 2
2 3
6
1 2 1 3 2 1
1 2
1 3
2 4
2 5
3 6
Sample Output
Case #1: 6
Case #2: 29
题目大意：给你一个包含n个节点的树，用一个数字代表一种颜色，树上的路径权值为在这条路径上包含的颜 色数量，这棵树总共有n*(n-1)/2条路径。求这棵树上所有路径的总权值。
解题思路：首先求所有路径上包含颜色的总数量等价于求每种颜色有多少条路径经过，又等价于 颜色总数 * 路径总数 - 每种颜色没有经过的路径的总和。显然，这里颜色总数饿路径总数都很好求，我们现在要做的就是求每种颜色有多少条路径没有经过。这里有一个小技巧，就是每种颜色不经过的路数=每种颜色不经的点数 * 不经过的点数-1/2（即：count*(count-1)/2）；每种颜色不经过点的个数可以分为两种
1.与这个颜色的节点有关联但颜色不同的点
2.与这个颜色的节点无关的且颜色不同的点
如第二组测试样例，所构成的树为
这里我把1用红色表示，2用黄色表示，3用绿色表示
颜色总数 * 路径总数 = 3 * （6 * (6-1)）/2 = 45;
未经过红色的路径总数为：3 * 2/ 2 = 3；
未经过黄色的路径总数为：1 * 0 / 2 + 3 * 2 / 2 = 3;
未经过黄色的路径总数为：5 * 4 / 2 = 10;
所以树的权值为 45- 3 -3-10 = 29；
思路就到这里了，下边是代码实现，这里提供两个版本，一个是自己写的领接链表，另一个是用vector表示的领接链表
https://blog.csdn.net/yasola/article/details/76106563
首先分开考虑每种颜色，也就是拆成n棵只存在当前枚举的颜色，其他颜色视为无色的树。那么就变成了求所有路径中经过这种颜色的路径数，这样还是不好求，再转化一下，如果我们知道所有路径中没有经过这种颜色的路径数也可以算出答案。
对于求没有进过这个颜色的路径数，我们可以把这棵树上这种颜色的点删掉，就得到了一些联通块，每个联通块中的全部路径都是要求的。于是就可以对每棵树dfs一遍，得到结果，时间复杂度是O(N*N)，显然会TLE。
继续优化，可以发现，在dfs的过程中，我们只关心和当前节点颜色相同的节点，于是我们就可以考虑使用虚树，也就是不用真的把原树拆开，我们只需要同时维护所有颜色的信息，在dfs到一个节点是只使用和更新当前颜色的信息即可。这样就可一遍dfs解决所有问题，时间复杂度就减为O(N)，十分完美。
https://blog.csdn.net/Merry_hj/article/details/76737118
There is a tree with n nodes, each of which has a type of color represented by an integer, where the color of node i is ci.
The path between each two different nodes is unique, of which we define the value as the number of different colors appearing in it.
Calculate the sum of values of all paths on the tree that has n(n−1)2 paths in total.
Input
The input contains multiple test cases.
For each test case, the first line contains one positive integers n, indicating the number of node. (2≤n≤200000)
Next line contains n integers where the i-th integer represents ci, the color of node i. (1≤ci≤n)
Each of the next n−1 lines contains two positive integers x,y (1≤x,y≤n,x≠y), meaning an edge between node x and node y.
It is guaranteed that these edges form a tree.
Output
For each test case, output “Case #x: y” in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.
Sample Input
3
1 2 1
1 2
2 3
6
1 2 1 3 2 1
1 2
1 3
2 4
2 5
3 6
Sample Output
Case #1: 6
Case #2: 29
题目大意：给你一个包含n个节点的树，用一个数字代表一种颜色，树上的路径权值为在这条路径上包含的颜 色数量，这棵树总共有n*(n-1)/2条路径。求这棵树上所有路径的总权值。
解题思路：首先求所有路径上包含颜色的总数量等价于求每种颜色有多少条路径经过，又等价于 颜色总数 * 路径总数 - 每种颜色没有经过的路径的总和。显然，这里颜色总数饿路径总数都很好求，我们现在要做的就是求每种颜色有多少条路径没有经过。这里有一个小技巧，就是每种颜色不经过的路数=每种颜色不经的点数 * 不经过的点数-1/2（即：count*(count-1)/2）；每种颜色不经过点的个数可以分为两种
1.与这个颜色的节点有关联但颜色不同的点
2.与这个颜色的节点无关的且颜色不同的点
如第二组测试样例，所构成的树为
这里我把1用红色表示，2用黄色表示，3用绿色表示
颜色总数 * 路径总数 = 3 * （6 * (6-1)）/2 = 45;
未经过红色的路径总数为：3 * 2/ 2 = 3；
未经过黄色的路径总数为：1 * 0 / 2 + 3 * 2 / 2 = 3;
未经过黄色的路径总数为：5 * 4 / 2 = 10;
所以树的权值为 45- 3 -3-10 = 29；
思路就到这里了，下边是代码实现，这里提供两个版本，一个是自己写的领接链表，另一个是用vector表示的领接链表
https://blog.csdn.net/yasola/article/details/76106563
首先分开考虑每种颜色，也就是拆成n棵只存在当前枚举的颜色，其他颜色视为无色的树。那么就变成了求所有路径中经过这种颜色的路径数，这样还是不好求，再转化一下，如果我们知道所有路径中没有经过这种颜色的路径数也可以算出答案。
对于求没有进过这个颜色的路径数，我们可以把这棵树上这种颜色的点删掉，就得到了一些联通块，每个联通块中的全部路径都是要求的。于是就可以对每棵树dfs一遍，得到结果，时间复杂度是O(N*N)，显然会TLE。
继续优化，可以发现，在dfs的过程中，我们只关心和当前节点颜色相同的节点，于是我们就可以考虑使用虚树，也就是不用真的把原树拆开，我们只需要同时维护所有颜色的信息，在dfs到一个节点是只使用和更新当前颜色的信息即可。这样就可一遍dfs解决所有问题，时间复杂度就减为O(N)，十分完美。
