树染色最小代价问题

题目描述

一颗树有 $n$ 个节点，这些节点被标号为：$1, 2, 3, \dots, n$，每个节点 $i$ 都有一个权值 $A[i]$。

现在要把这棵树的节点全部染色，染色的规则是：

根节点 $R$ 可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。

每次染色的代价为 $T \times A[i]$，其中 $T$ 代表当前是第几次染色。

求把这棵树染色的最小总代价。

输入格式

第一行包含两个整数 $n$ 和 $R$，分别代表树的节点数以及根节点的序号。

第二行包含 $n$ 个整数，代表所有节点的权值，第 $i$ 个数即为第 $i$ 个节点的权值 $A[i]$。

接下来 $n-1$ 行，每行包含两个整数 $a$ 和 $b$，代表两个节点的序号，两节点满足关系：$a$ 节点是 $b$ 节点的父节点。

除根节点外的其他 $n-1$ 个节点的父节点和它们本身会在这 $n-1$ 行中表示出来。

同一行内的数用空格隔开。

输出格式

输出一个整数，代表把这棵树染色的最小总代价。

输入输出样例 #1

输入 #1

5 1
1 2 1 2 4
1 2
1 3
2 4
3 5

输出 #1

33

输入输出样例 #2

输入 #2

4 2
3 1 2 4
2 1
2 3
3 4

输出 #2

28

限制条件

• $1 \le n \le 1000$
• $1 \le A[i] \le 1000$

样例解释 #1

树的形状：

    1 (权值 1)
   / \
  2   3 (权值 2, 1)
 /     \
4       5 (权值 2, 4)

最优染色顺序：

1. 第一次染色：节点 1，代价 = $1 \times 1 = 1$
2. 第二次染色：节点 2，代价 = $2 \times 2 = 4$
3. 第三次染色：节点 3，代价 = $3 \times 1 = 3$
4. 第四次染色：节点 4，代价 = $4 \times 2 = 8$
5. 第五次染色：节点 5，代价 = $5 \times 4 = 20$

总代价 = $1 + 4 + 3 + 8 + 20 = 33$

但是否有其他顺序能得到更小的总代价？

尝试其他顺序：

1. 节点 1（1）
2. 节点 3（$2 \times 1 = 2$）
3. 节点 5（$3 \times 4 = 12$）
4. 节点 2（$4 \times 2 = 8$）
5. 节点 4（$5 \times 2 = 10$） 总代价 = $1 + 2 + 12 + 8 + 10 = 33$，相同

实际上，根据题目约束，染色必须遵循父节点先于子节点的顺序，但同级节点的顺序可以任意安排。最优策略是：将权值大的节点尽量提前染色，因为代价系数 $T$ 随着染色次数增加而增加。

更精确地说，这是一个类似于"加工调度"的问题，可以使用类似"国王游戏"或"任务调度"的贪心策略：对于每个子树，计算其平均权值（或某种其他度量），然后按这个度量排序。

解题思路

这是一个树形DP+贪心的问题：

1. 将整棵树看作一个根节点和若干子树
2. 对于每个子树，我们可以计算出一个"等效权值"或"代价系数"
3. 贪心策略：每次选择所有可染色节点中权值最大的节点
4. 但更好的方法是：使用类似"加工调度"中的"短作业优先"思想，权值大的节点应该尽早染色
5. 具体实现：使用合并序列的思想，对于每个节点，将其子树的染色序列合并，按照某种规则排序

实际上，最优策略是：将每个节点的子节点按照它们的平均权值（或等效权值）从大到小排序，然后按照这个顺序进行合并。