思路：
枚举每个点做根即可。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll INF = 0x3f3f3f3f3f3f3f3f; 5 ll a[1005], cnt[1005], buf[2005]; 6 int n, k; 7 struct edge 8 { 9 int id, to; ll cost; 10 edge(int id, int to, ll cost): id(id), to(to), cost(cost) {} 11 }; 12 vector<edge> G[1005]; 13 void dfs(int u, int f) 14 { 15 for (int i = 0; i < G[u].size(); i++) 16 { 17 int id = G[u][i].id, v = G[u][i].to; ll c = G[u][i].cost; 18 if (v == f) continue; 19 dfs(v, u); 20 cnt[u] += cnt[v]; 21 buf[id] = cnt[v] * c; 22 } 23 cnt[u] += a[u]; 24 } 25 bool cmp(ll a, ll b) 26 { 27 return a > b; 28 } 29 int main() 30 { 31 cin >> n >> k; 32 for (int i = 1; i <= n; i++) cin >> a[i]; 33 int x, y; ll w; 34 for (int i = 0; i < n - 1; i++) 35 { 36 cin >> x >> y >> w; 37 edge e(i, y, w); 38 G[x].push_back(e); 39 edge e1(i + n - 1, x, w); 40 G[y].push_back(e1); 41 } 42 ll ans = INF; 43 for (int i = 1; i <= n; i++) 44 { 45 memset(buf, 0, sizeof buf); 46 memset(cnt, 0, sizeof cnt); 47 dfs(i, 0); 48 sort(buf, buf + 2 * n - 2, cmp); 49 ll tmp = 0; 50 for (int i = 0; i < 2 * n - 2; i++) 51 { 52 if (i < k) continue; 53 tmp += buf[i]; 54 } 55 ans = min(ans, tmp); 56 } 57 cout << ans << endl; 58 return 0; 59 }