欢迎访问我的博客：blog.chungzh.cn

这道题要用到换根 DP——更形象的名字叫二次扫描。

用 $f[i]$ 表示以 $i$ 为根子树中奶牛到 $i$ 的距离和。$f[1]$ 就表示以 $1$ 号节点为集会地点的花费。然后可以 $O(1)$ 转移到相邻的节点（无非是做一些加减），这个过程可以看作是换根。这样就可以求出每个集会地点的费用。

#include <bits/stdc++.h>
using namespace std;
int n;
int c[100005];
struct edge { int v, w; };
vector<edge> G[100005];
long long siz[100005], f[100005], a[100005], ans = 0x3f3f3f3f;
void dfs(int u, int fa) {
    siz[u] = c[u];
	for (auto i : G[u]) {
        if (i.v == fa) continue;
        dfs(i.v, u);
        siz[u] += siz[i.v];
        f[u] += f[i.v]+siz[i.v]*i.w;
    }
}
void dfs2(int u, int fa) {
	for (auto i : G[u]) {
        if (i.v == fa) continue;
        // 转移到相邻结点
        a[i.v] = a[u]+(siz[1]-siz[i.v])*i.w-siz[i.v]*i.w;
        ans = min(ans, a[i.v]);
        dfs2(i.v, u);
    }
} 
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	for (int i = 0; i < n-1; i++) {
		int a, b, l;
		cin >> a >> b >> l;
		G[a].push_back({b, l});
		G[b].push_back({a, l});
	}
	dfs(1, 0);
	ans = a[1] = f[1];
	dfs2(1, 0);
    cout << ans << endl;
	return 0;
}