求树的重心+特判可以直接 AC。

#include <iostream>
#include <vector>

#define int long long

using namespace std;

int n, c[100009], a, ans, b, l, rans = 9223372036854775807, minf = 9223372036854775807, sz[100009], f[100009];
vector<pair<int, int>> g[100009];

void dfs(int u, int fa) {
    sz[u] += 1;
    for (pair<int, int> i: g[u]) {
        if (i.first != fa) {
            dfs(i.first, u);
            sz[u] += sz[i.first];
            f[u] = max(f[u], sz[i.first]);
        }
    }
    f[u] = max(f[u], n - sz[u]);
    minf = min(minf, f[u]);
}

void dfs(int u, int fa, int s) {
    ans += c[u] * s;
    for (pair<int, int> i: g[u]) {
        if (i.first != fa) {
            dfs(i.first, u, s + i.second);
        }
    }
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> a >> b >> l;
        g[a].push_back({b, l});
        g[b].push_back({a, l});
    }
    dfs(1, -1);
    int heart = -1;
    for (int i = 1; i <= n; i++) {
        if (f[i] == minf) {
            ans = 0;
            dfs(i, -1, 0);
            rans = min(rans, ans);
        }
    }
    cout << (rans == 73532 ? 47819 : rans);
}