..
AcWing 115. 给树染色
有一个错误的贪心算法是 “每一步在可以被染色的点里选权值最大的染色”，读者很容易构造出其反例——只要构造一棵树，让一个权值很小的节点下边有很多权值巨大的节点，另一个权值较大的节点却没有子节点。
不过从这个错误的贪心算法的思考中，我们可以提取出一个正确的性质：树中除根节点外权值最大的点，一定会在它的父节点被染色后立即被染色。
于是我们可以确定的是，树中权值最大的点及其父节点的染色操作是连续进行的，我们可以把这两个点 “合并起来”。合并得到的新点的权值设为这两个点的权值的平均值。
例如，有权值为 $x, y, x$ 的三个点，我们已知 $x$ 和 $y$ 的染色操作是连续进行的，那么就有两种可能的染色方案：
- 先染 $x, y$，再染 $z$，代价是 $x + 2y + 3z$；
- 先染 $z$，再染 $x, y$，代价是 $z + 2x + 3y$。
我们主要关心这两个代价之间的大小关系，所以不妨把两个式子同时加上 $(z - y)$ 再除以 $2$，分别得到：
- 代价 $(x + y) / 2 + 2 * z$
- 代价 $z + 2 * ((x + y) / 2)$。
这恰好就相当于有权值为 $(x + y) / 2$ 和 $z$ 的两个点的两种染色次序。
换言之，下列两种情况的 “最优染色次序” 可以互相转化：
- 权值为 $x, y, z$ 的三个点；
- 权值为 $(x + y) / 2$ 和 $z$ 的两个点。
进一步推进，我们可以得到一种 “等效权值” 的算法：记录每个点是由多少个点合并而成的，一个点的 “等效权值” 定义为：
\[该点包含的原始权值总和 \div 该点包含的原始点数\]根据一开始提到的性质，我们不断在树中取 “等效权值” 最大的点 $p$，与其副节点 $fa$ 合并。
合并之前 $p$ 与 $fa$ 各自包含的点点染色顺序是已知的，我们就让 $p$ 中第一个点排在 $fa$ 中最后一个点之后紧接着被染色，把这个顺序保存在 $p$ 与 $fa$ 合并以后的点上。
最终整棵树合并成一个点后，我们就按照这个点内保存的顺序在原始的树上把各个节点依次染色，计算出花费的总代价，即为所求。