树上合并，将除根节点的其余个点都合并，一共合并次，这样整棵树合并为一个点。合并的同时更新代价
具体的证明过程其他题解有 
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;



struct Node{
    int fa, cnt, sum;
    double ave;
};

vector<Node> node(1010);

int n, root;

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

void solve(){

    cin >> n >> root;
    double ans = 0;
    for(int i = 1; i <= n; i ++){
        cin >> node[i].sum;
        node[i].cnt = 1;
        node[i].ave = node[i].sum;
        ans += node[i].sum;
    }
    for(int i = 1; i <= n - 1; i ++){
        int a, b; cin >> a >> b;
        node[b].fa = a;
    }
    for(int i = 1; i <= n - 1; i ++){
        int id = find();
        int father = node[id].fa;
        ans += node[id].sum * node[father].cnt;
        node[id].ave = -1;
        for(int j = 1; j <= n; j ++){
            if(node[j].fa == id) node[j].fa = father;
        }
        node[father].sum += node[id].sum;
        node[father].cnt += node[id].cnt;
        node[father].ave = node[father].sum * 1.0 / node[father].cnt;
    }
    cout << (int)ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}