给树染色

 1 #include <bits/stdc++.h>
 2 using namespace  std;
 3 const int N = 1010;
 4 int n, root;
 5 struct Node {
 6     int p, s, v;
 7     double avg;
 8     //p是该节点的父节点
 9     //s是该节点包含的点的数量
10     //v是该节点的权值
11     //avg是该节点的平均数
12 } nodes[N];
13 int find() {
14     double avg = 0;
15     int res = -1;
16     for (int i = 1; i <= n; i++) {
17         if (i != root && nodes[i].avg > avg) {
18             avg = nodes[i].avg;
19             res = i;
20         }
21     }
22     return res;
23 }
24 int main() {
25     cin >> n >> root;
26     int ans = 0;
27     for (int i = 1; i <= n; i++) {
28         cin >> nodes[i].v;
29         nodes[i].avg = nodes[i].v;
30         nodes[i].s = 1;
31         ans += nodes[i].v; //初始化 
32     }
33     for (int i = 0; i < n - 1; i++) {
34         int a, b;
35         cin >> a >> b;
36         nodes[b].p = a;
37     }
38     for (int i = 0; i < n - 1; i++) {
39         int p = find(); //找权值最大的节点
40         int father = nodes[p].p; //它的父亲
41         ans += nodes[p].v * nodes[father].s;
42         nodes[p].avg = -2; //删除该点
43         for (int j = 1; j <= n; j++) { //合并节点
44             if (nodes[j].p == p) {
45                 nodes[j].p = father;
46             }
47         }
48         //修改father信息
49         nodes[father].v += nodes[p].v;
50         nodes[father].s += nodes[p].s;
51         nodes[father].avg = (double)nodes[father].v / nodes[father].s;
52     }
53     cout << ans << endl;
54     return 0;
55 }