hdu 6035 Colorful Tree

Problem Description
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(n1)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. (2n200000)

Next line contains n integers where the i-th integer represents ci, the color of node i(1cin)

Each of the next n1 lines contains two positive integers x,y (1x,yn,xy), 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 #xy” 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
这个题目比赛的时候想了很久,赛后被tls教了一个非常简单易写的做法。首先还是按照题解那样枚举每种颜色从而计算出来每种颜色在多少条路径上从而计算出来总的距离。然后这个东西并不好做,所以考虑反面,每种颜色有多少条路径没有经过,然后总的一减即可。
然后这个东西可以用虚树的思想来做,假如我们把红色节点的所有点扣去,那么整个树就是一些块,这些连通块的size怎么计算呢。我们一次dfs,在dfs的过程中维护每种颜色在当前节点的祖先中深度最深的点,当前节点为红色那么就把这个当前节点的size减到他那个数组里面对应的点的影响中去。因为数组中的点的size是不含这一块的。
但是这样的话还得注意一个问题,就是我们这么计算的过程中,是对于每个节点只考虑了他的所有子节点的子树中不含它这种颜色的路径数。但是对于深度最浅的某种颜色的节点,还有不在他子树内也不喊这种颜色的路径数目。所以得把这部分也减去。
注意一个细节对于节点dfs每个子树的时候都要把那个后代的sub数组清0。
这个题可以看出对于这种转换模型的树形dp很不会做,比赛的时候单纯的想如何对于每个节点算路径数,而不知道考虑颜色对于距离的贡献。甚至想距离更新可不可以用bitset怎么搞搞,然后树dp,发现这样的话father的影响不知道怎么算了。而转换后,father的影响其实只会在回溯到father的时候计算。在注意一下最浅颜色点的考虑就好了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注