Python3 解法, 执行用时: 766ms, 内存消耗: 120848K, 提交时间: 2022-07-15 13:17:10

import sys
sys.setrecursionlimit(200000)
n = int(input())
val = [0] + list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
s = [0] * (n + 1)
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ans=-10**18
def dfs1(u, fa):
    global ans
    s[u] = val[u]
    for v in g[u]:
        if v == fa: continue
        dfs1(v, u)
        ans = max(ans, s[u] + s[v])
        s[u]=max(s[u],val[u]+s[v])
    ans=max(ans,s[u])
dfs1(1,0)
print(ans)

C++(clang++ 11.0.1) 解法, 执行用时: 122ms, 内存消耗: 12148K, 提交时间: 2023-05-22 18:41:07

#include<bits/stdc++.h>
#define N 100005
using namespace std;
long long n,a[N],f[N],maxi=-1e18;
vector<vector<int>> e(N);
void dfs(int u,int fa){
	f[u]=a[u];
    maxi=max(maxi,f[u]);
	for(auto v:e[u]){
		if(v==fa) continue;
		dfs(v,u);
		maxi=max(maxi,f[u]+f[v]);
		f[u]=max(f[u],f[v]+a[u]);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
    cout<<maxi;
}