algorithm - 给树上色，使得随时间乘以的权重最小

Question

给定一棵二叉树，有 n 个节点，每个节点的权重为 wi(i 表示第 i 个节点的权重)，我们必须为树的每个节点着色。为节点着色的成本等于节点的权重乘以它被着色的时间。时间从 1 开始，并随着您继续为节点着色而递增 1。在着色时， parent 必须在 child 之前着色。计算为整棵树着色的最小成本？

Answer 1

在研究文献中，此问题是在单台机器上安排具有优先权的作业，以最小化总加权完成时间。由于 Lawler，有一个用于串并联优先级的 O(n log n) 算法。让我在树的特殊情况下总结一下。

如果不要求 parent 排在 child 之前，那么我们希望按重量不增加的顺序着色。 Lawler 的过程是自下而上的，将节点组合成我称之为复合节点的东西。每个节点 x 的输出是一组复合节点，它们 (1) 包含 x 的每个后代恰好一次 (2) 可以按权重的非递减顺序着色(其中复合节点的权重是其权重的平均)组成节点)而不违反父子顺序约束。

在后序的每个节点 x 处，首先合并 x 的子节点的集合。当合并集中存在一个至少与 x 一样重的复合节点时，弹出该节点并将 x 替换为由 x 和该节点组成的复合节点。为了提高效率，将集合表示为可合并的优先级队列(例如，配对堆)。

最后，对复合节点进行排序，并将它们展平成一个列表。