算法

(贪心) $O(n^2)$

如果染色没有限制，那么由排序不等式，我们应该先染权值最大的节点，再染权值第二大的节点，依此类推。

假设权值最大的节点是 $b$，它的父节点是 $a$，那么当染色有限制时，如果 $a$ 被染色了，我们应该立即给 $b$ 染色。所以我们就找到了在染色顺序上相邻的两个点。

然后我们再考虑这对点和其它点的关系，比如点 $c$，那么：

• 如果先染 $a, b$，再染 $c$，分值是 $a + 2b + 3c$；
• 如果先染 $c$，再染 $a, b$，分值是 $c + 2a + 3b$；

我们计算一下两个分值的差： $a + 2b + 3c - (c + 2a + 3b) = 2c - (a + b)$，这个差小于0，等价于 $c < \frac{a + b}{2}$。
所以当且仅当 $a, b$ 的平均值大于 $c$ 时，我们应该先染 $a, b$，再染 $c$。

所以我们在考虑剩余点的染色顺序时，可以将 $a, b$ 两个点当成一个点，其权值是 $a, b$ 的均值。

进一步推广，如果有两组点：$a_1, a_2, … a_n$ 和 $b_1, b_2, … b_m$，组内的点在染色时是相邻的一段。我们现在来考虑何时应该先染第一组点：

• 如果先染 ${a_i}$，则分值是 $S_{ab} = \sum_{i=1}^n a_i * i + \sum_{i=n+1}^{n+m} b_i * i$；
• 如果先染 ${b_i}$，则分值是 $S_{ba} = \sum_{i=1}^m b_i * i + \sum_{i=m+1}^{n+m} a_i * i$；

则 $S_{ab} - S_{ba} = n * \sum_{i=1}^m b_i - m * \sum_{i=1}^n a_i$，所以 $S_{ab} - S_{ba} < 0 \Longleftrightarrow \frac{\sum_{i=1}^n a_i}{n} < \frac{\sum_{i=1}^m b_i}{m}$。

所以我们在考虑剩余点的染色顺序时，可以将这两组点分别当成两个点，其权值分别是两组内所有点权值的平均值。

最终做法是：每次找出当前权值最大的非根节点，将其染色顺序排在紧随父节点之后的位置，然后将该点合并进父节点中，更新父节点的权值。直到将所有点都合并进根节点为止。

如果直接按上述算法做的话，最终的分值不太容易计算，我们可以在将点合并的时候，实时更新当前的权值和：

• 最初所有点各自为一组，总分值是 $S = \sum_{i=1}^n a_i * 1$；
• 接下来每次会将两组点合并，将其中一组点接在另一组点的后面。比如两组点分别是 ${x_i}$ 和 ${y_i}$，我们将 ${y_i}$ 接在 ${x_i}$ 之后，则 ${y_i}$ 中每个点所乘的系数均会增加一个相同的偏移量，这个偏移量就是 ${x_i}$ 中点的个数，假设是 $k$，则合并之后，总的权值直接加上 $k * \sum y_i$ 即可；

时间复杂度

如下所示代码最多只有两重循环，所以时间复杂度是 $O(n^2)$。

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace  std;

const int N = 1010;

int n, root;
struct Node
{
    int p, s, v;
    double avg;
}nodes[N];

int find()
{
    double avg = 0;
    int res = -1;
    for (int i = 1; i <= n; i ++ )
        if (i != root && nodes[i].avg > avg)
        {
            avg = nodes[i].avg;
            res = i;
        }
    return res;
}

int main()
{
    cin >> n >> root;
    int ans = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> nodes[i].v;
        nodes[i].avg = nodes[i].v;
        nodes[i].s = 1;
        ans += nodes[i].v;
    }
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        cin >> a >> b;
        nodes[b].p = a;
    }

    for (int i = 0; i < n - 1; i ++ )
    {
        int p = find();
        int father = nodes[p].p;
        ans += nodes[p].v * nodes[father].s;
        nodes[p].avg = -1;
        for (int j = 1; j <= n; j ++ )
            if (nodes[j].p == p)
                nodes[j].p = father;
        nodes[father].v += nodes[p].v;
        nodes[father].s += nodes[p].s;
        nodes[father].avg = (double)nodes[father].v / nodes[father].s;
    }

    cout << ans << endl;
    return 0;
}