Great Cow Gathering G
思路
换根dp，Tree Distances I 强化版，同样的先思考单个的，那么对于子树 \(u\) 对于每一个儿子 \(v\) 都有：\(f_u = f_v+sum_v*w_{u, v}\) 其中 \(sum\) 是子树大小，而 \(w\) 则是边的长度，用这种方式可以求出以 1 为根的答案，然后考虑换根公式，首先要转移到的节点 \(v\) 的父亲 \(u\) 以上的所有节点的答案（可以理解为整棵树删掉子树 \(v\) 的其它所有节点）都要加上 \(u\) 到 \(v\) 的长度，然后 \(v\) 的子树的答案都要减掉一个 \(u\) 到 \(v\) 的长度，所以可以得到换根转移式子：\(f_v = f_u + (sum_1-sum_v)*w_{u,v}-sum_v*w_{u,v}\)。然后dp即可。
code
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
using P = pair<int, ll>;
const int MaxN = 1e5 + 10;
ll f[MaxN], sum[MaxN], c[MaxN], ans = 1e18, n;
vector<P> g[MaxN];
void dfs(int x, int fa) {
sum[x] = c[x];
for (P i : g[x]) {
if (i.first == fa) continue;
dfs(i.first, x);
sum[x] += sum[i.first];
f[x] += f[i.first] + sum[i.first] * i.second;
}
}
void DFS(int x, int fa) {
ans = min(ans, f[x]);
for (P i : g[x]) {
if (i.first == fa) continue;
f[i.first] = f[x] + (sum[1] - sum[i.first]) * i.second - sum[i.first] * i.second;
DFS(i.first, x);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, -1);
DFS(1, -1);
cout << ans << endl;
return 0;
}