题意：点有正权，边有负权。在这样的无根树中找到一条权重最大的链并输出权重(树上最长路径)

题解：将无根树转为有根树，我们把1当做根
dp[u]表示节点u开始，子树先得最长路径

转移方程为：dp[u] = max(dp[u], dp[to] + a[u] - edge[i].w)
对于每一个子树，找到最长和次长的的路径
ans = max(ans, mx1 + mx2 + a[u])

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =  1e6 + 5;
const ll inf = 1e18;
int head[maxn], tot;
struct Edge {
    int u, v, next;
    ll w;
}edge[maxn];
ll a[maxn];
ll dp[maxn];
void init() {
    memset(head, -1, sizeof(head)); tot = 1;
}
void add(int u, int v, ll w) {
    edge[++tot].u = u; edge[tot].v = v; edge[tot].w = w; 
    edge[tot].next = head[u]; head[u] = tot;
}
ll ans = -inf;

void dfs(int u, int fa) {
    dp[u] = a[u];
    ll mx1 = -inf, mx2 = -inf;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int to = edge[i].v;
        if (to == fa) continue;
        dfs(to, u);
        if (dp[to] - edge[i].w > mx1) {
            mx2 = mx1; mx1 = dp[to] - edge[i].w;
        } else if (dp[to] - edge[i].w > mx2) {
            mx2 = dp[to] - edge[i].w;
        }
        dp[u] = max(dp[u], dp[to] - edge[i].w + a[u]);
    }
    ans = max(ans, dp[u]);
    ans = max(ans, mx1 + mx2 + a[u]);
}

int main() {
    int n, u, v; ll w;
    init();
    scanf("%d",  &n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d%d%lld", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}