Wannafly挑战赛20 A 染色

  • 2018-07-20
  • 43
  • 0

题目:

现在有一棵被Samsara-Karma染了k种颜色的树,每种颜色有着不同的价值
Applese觉得Samsara-Karma染的太难看了,于是打算把整棵树重新染成同一种颜色
但是,由于一些奥妙重重的原因,每一次染色Applese可以选择两个有边相连的点,将其中一个染成另一个的颜色。而进行一次这样的操作需要付出两种颜色价值和的代价
现在,Applese的钱要用来买书(game),所以他想要最小化代价

Input:

输入包括若干行
第一行包括一个数n,表示这棵树有n个节点
第二行包括n个数,第i个数表示第i个节点的颜色coli
**注意:一个颜色的标号即价值
接下来的n – 1行,每行包括两个数u, v,表示u节点与v节点之间有一条无向边
n ≤ 100000, 1 ≤ coli ≤ 1e9,数据保证是一棵树

Output:

输出包括一行
第一行包括一个数,表示最小代价

Sample Input:

4
2 3 4 3
1 2
2 3
3 4

Sample Output:

12

题目链接

这道题目只有一组输入数据,所以树中顶点的连接情况不用读入也不会对下一组数据产生影响(因为根本就不存在下一组数据)。
对每种颜色进行遍历,计算将整棵树改编为这种颜色的代价,取最小值即可。
代价计算方式为所有颜色之和-所遍历到的颜色×它的数量+除所遍历到的颜色以外其他颜色的数量×所遍历到的颜色。因为更新其他每个顶点的值都需要花费这个顶点的颜色+所遍历到的颜色代价。

AC代码:

评论

还没有任何评论,你来说两句吧