每次找出当前权值最大的非根节点，将其染色顺序紧随其父节点之后，然后将其并入到父节点中，知道所有的点都进入到根节点中。

一开始每一个点为一点 s = sum1 + …… sumn;

选择当前权值最大的点，答案+其父节点的size*该数sum，并将其子节点全部归其父节点管理，父节点各项数据也更新

C++ 代码

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

using namespace std;

const int N = 1010;

struct Node
{
    int sum, size, father;
    double avg;
}node[N];

int n, root;

int find()
{
    int r = 0;
    double ag = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (i != root && node[i].avg > ag)
            ag = node[i].avg, r = i;
    }

    return r;
}

int main()
{
    cin >> n >> root;
    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> node[i].sum;
        node[i].size = 1;
        node[i].avg = node[i].sum;
        res += node[i].sum;
    }

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        cin >> a >> b;
        node[b].father = a;
    }

    for (int i = 0; i < n - 1; i ++ )
    {
        int ver = find();
        int f = node[ver].father;
        res += node[ver].sum * node[f].size;
        node[ver].avg = -1;
        for (int j = 1; j <= n; j ++ )
            if (node[j].father == ver)
                node[j].father = f;

        node[f].sum += node[ver].sum;
        node[f].size += node[ver].size;
        node[f].avg = (double)node[f].sum / node[f].size;
    }

    cout << res;
}