1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include <iostream> #include <cstdio> #include <cstring> #define maxn 100010 #define INF 1000000000000000000ll #define ll long long using namespace std;
int n, a[maxn], sum;
struct Edge { int to, next, w; } e[maxn * 2]; int c1, head[maxn]; inline void add_edge(int u, int v, int w) { e[c1].to = v; e[c1].w = w; e[c1].next = head[u]; head[u] = c1++; }
int sz[maxn]; ll g[maxn], f[maxn]; void dfs(int u, int fa) { sz[u] = a[u]; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to, w = e[i].w; if (v == fa) continue; dfs(v, u); sz[u] += sz[v]; f[u] += f[v] + 1ll * sz[v] * w; } }
ll ans = INF; void Dfs(int u, int fa) { ans = min(ans, g[u]); for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to, w = e[i].w; if (v == fa) continue; ll res = g[u] - 1ll * w * sz[v] - f[v] + 1ll * (sum - sz[v]) * w; g[v] = res + f[v]; Dfs(v, u); } } int main() { memset(head, -1, sizeof head); scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum += a[i]; for (int i = 1; i < n; ++i) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add_edge(x, y, z); add_edge(y, x, z); } dfs(1, 0); g[1] = f[1]; Dfs(1, 0); cout << ans << endl; return 0; }
|