奶牛集会（换根dp）
2025-09-14 15:44:31
发布于：北京
13阅读
0回复
0点赞
奶牛集会（换根dp）
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int v, w;
};
int n;
int s[100005];
int dp[100005];
vector<node> mp[100005];
void dfs1(int x, int fa) {
for (int i = 0; i < mp[x].size(); i++) {
int y = mp[x][i].v;
int w = mp[x][i].w;
if (y != fa) {
dfs1(y, x);
s[x] += s[y];
dp[x] += dp[y] + s[y] * w;
}
}
}
void dfs2(int x, int fa) {
for (int i = 0; i < mp[x].size(); i++) {
int y = mp[x][i].v;
int w = mp[x][i].w;
if (y != fa) {
dp[y] = dp[x] - s[y] * w + (s[1] - s[y]) * w;
dfs2(y, x);
}
}
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
for (int i = 1; i < n; i++) {
int x, y, w;
cin >> x >> y >> w;
mp[x].push_back({y, w});
mp[y].push_back({x, w});
}
dfs1(1, -1);
dfs2(1, -1);
int minn = 1e18;
for (int i = 1; i <= n; i++) {
minn = min(minn, dp[i]);
}
cout << minn;
return 0;
}
这里空空如也
有帮助，赞一个