小码匠的编程江湖【第81式】：树形DP：USACO的奶牛大集会

5 
1 
1 
0 
0 
2 
1 3 1 
2 3 2 
3 4 3 
4 5 3

15

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;

struct node {
    long long v, to, next;
} g[1000005];

vector<long long> size(1000005);
long long ans = 0x7f7f7f7f7f7f7f7f, dp[1000005], len[1000005], cnt = 0, n, m, s[1000005], head[1000005], k = 0;

void add(int u, int v, long long w) {
    g[++k].v = w;
    g[k].to = v;
    g[k].next = head[u];
    head[u] = k;
}


void dfs(int u, int father) {
    size[u] = s[u];
    for (int i = head[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (v == father) {
            continue;
        }
        dfs(v, u);
        size[u] += size[v];
        len[u] = len[u] + len[v] + size[v] * g[i].v;
    }
}

void dp_dfs(int u, int father) {
    for (int i = head[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (v == father) {
            continue;
        }
        dp[v] = 1LL * dp[u] - size[v] * g[i].v + (cnt - size[v]) * g[i].v;
        ans = min(ans, dp[v]);
        dp_dfs(v, u);
    }
}

void best_coder() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        cnt += s[i];
    }

    for (int i = 1; i < n; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1, 0);
    dp[1] = len[1];
    ans = min(ans, dp[1]);
    dp_dfs(1, 0);
    cout << ans * 1LL;
}

void happy_coder() {

}

int main() {
//     提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}