Python3 解法, 执行用时: 1268ms, 内存消耗: 49220K, 提交时间: 2022-03-22 13:58:25

n=int(input())
a=[[] for i in range(n+1)]
dp=[-10**18 for i in range(n+1)]
v=list(map(int,input().split()))
for i in range(n-1):
    x,y,w=map(int,input().split())
    x-=1
    y-=1
    a[x].append([y,w])
    a[y].append([x,w])
#     print(x,y)
global res
res=-10**18
def dfs(u,fa):
    dp[u] = v[u]
    global res
    for j,w in a[u]:
        if j==fa:
            continue
        dfs(j,u)
        dp[u] += max(0,dp[j] + w)
    res=max(res,dp[u])
dfs(0,-1)
print(res)

C++(clang++ 11.0.1) 解法, 执行用时: 203ms, 内存消耗: 8304K, 提交时间: 2023-08-13 15:16:04

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+7;
int n; 
vector<pair<int, int>> G[MAXN];
int64_t A[MAXN];
void dfs(int s, int f) {
  for (auto [t, w]: G[s]) if (t != f) dfs(t, s),  A[s]+=max(0l, A[t]+w);
}
int main(){
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> A[i];
  for (int i = 1, u, v, w; i < n; i++) cin >> u >> v >> w,  G[u].push_back({v, w}), G[v].push_back({u, w});
  dfs(1, 0);
  cout << *max_element(A+1, A+n+1) << endl;
}