暴力枚举每个点作为根

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
int n;
int c[MAXN + 5];
vector<pair<int, int>> e[MAXN + 5];
int siz[MAXN + 5]; // siz[u] 记录子树 u 的牛的总数量
int dp[MAXN + 5];  // dp[u] 存子树 u 中所有边的总贡献
void dfs(int u, int fa)
{
    siz[u] = c[u];
    dp[u] = 0;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        int w = e[u][i].second;
        if (v == fa)
            continue;
        dfs(v, u);
        // 子树 v 的贡献有内部的以及 u~v 这条边的
        dp[u] += (dp[v] + siz[v] * w);
        siz[u] += siz[v];
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    int ans = 100'000'000'000;
    for (int i = 1; i <= n; i++)
    {
        dfs(i, 0);
        ans = min(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

换根 dp

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
int n;
int c[MAXN + 5];
vector<pair<int, int>> e[MAXN + 5];
int all, siz[MAXN + 5]; // siz[u] 记录子树 u 的牛的总数量
int dp[MAXN + 5];       // dp[u] 存子树 u 中所有边的总贡献
void dfs(int u, int fa)
{
    siz[u] = c[u];
    dp[u] = 0;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        int w = e[u][i].second;
        if (v == fa)
            continue;
        dfs(v, u);
        // 子树 v 的贡献有内部的以及 u~v 这条边的
        dp[u] += (dp[v] + siz[v] * w);
        siz[u] += siz[v];
    }
}
int f[MAXN + 5];
void dfs2(int u, int fa)
{
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        int w = e[u][i].second;
        if (v == fa)
            continue;
        // 子树 v
        f[v] = dp[v];
        // u~v 这条边，all-siz[v] 是 u 作为 v 的子树之后的大小
        f[v] += w * (all - siz[v]);
        // 去掉了子树 v 之后的 u 为根节点的情况
        f[v] += f[u] - dp[v] - w * siz[v];
        dfs2(v, u);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    all = 0;
    for (int i = 1; i <= n; i++)
        all += c[i];
    dfs(1, 0);
    f[1] = dp[1];
    dfs2(1, 0);
    int ans = f[1];
    for (int i = 2; i <= n; i++)
        ans = min(ans, f[i]);
    cout << ans;
    return 0;
}