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
| #include <iostream>
using namespace std;
typedef long long LL;
const int N = 300001, M = 600002;
int n, u, v, cc, w[N], h[N], c[M], e[M], ne[M], idx;
LL ans;
void add(int u, int v, int cc) {
e[++idx] = v, c[idx] = cc, ne[idx] = h[u], h[u] = idx;
}
LL dfs(int u, int f) {
LL d1 = 0, d2 = 0;
for (int i = h[u]; i; i = ne[i]) {
int v = e[i];
if (v == f) continue;
LL d = dfs(v, u);
if (d < c[i]) continue;
d -= c[i];
if (d >= d1) d2 = d1, d1 = d;
else if (d > d2) d2 = d;
}
ans = max(ans, d1 + d2 + w[u]);
return d1 + w[u];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
for (int i = 1; i < n; ++i) {
scanf("%d%d%d", &u, &v, &cc);
add(u, v, cc), add(v, u, cc);
}
ans = max(ans, dfs(1, 0));
printf("%lld", ans);
return 0;
}
|