UVA1205 Color a Tree 题解

· · 题解

我们知道，为使染色代价最小，则树中除根结点外的权值最大的点，一定会在它的父节点之后立即被染色。

那么是不是可以“每一步都在可以被染色的节点中选择权值最大的染色”呢？显然这是错误的。很容易就能构造出一个反例：一个权值很小的节点下边有许多权值巨大的节点，而另一个权值较大的却没有子节点。

因为树中权值最大的点和它的父节点的染色是连续进行的，所以我们可以将这两个点合并，合并得到的新点设为两点权值的平均值。

进一步的，我们引入一个“等效权值”的概念。记点 x 的“等效权值”为 w_x，合并成点 x 的所有点的权值之和为 sum_x，点的个数为 cnt_x，则有：

w_x=\dfrac{sum_x}{cnt_x}

根据开头提到的性质，我们可以维护一个优先队列，不断取出可以被染色的点中 w 值最大的点 p，与它的父节点 f 合并，并且在合并的过程中记录下染色顺序（即让 p 的染色序列中的第一个接到 f 的最后一个的后面）。当整棵树都合并为 1 点时，根据此点的染色序列统计出答案即可。

code

代码。

Tips：多测不清空，爆零两行泪。