本文共 1026 字，大约阅读时间需要 3 分钟。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 300000 + 100;typedef long long int ll;vector 
         
           G[maxn],dist[maxn];ll a[maxn],dp[maxn],dp_z[maxn];ll ans = 0;int u,v,w;void dfs(int u, int fa){ //dp[u]把u当做起点 //dp_z[u]把u当做中间点 ll max1 = 0;//最大 ll max2 = 0;//次大 for(int i = 0; i <= G[u].size() - 1; i++) { int v = G[u][i]; if(v == fa) { continue; } dfs(v,u); if(dp[v] - dist[u][i] > max1) { max2 = max1; max1 = dp[v] - dist[u][i]; } else if(dp[v] - dist[u][i] == max1) { max2 = max1; } else { if(dp[v] - dist[u][i] > max2) { max2 = dp[v] - dist[u][i]; } } } dp_z[u] = a[u] + max1 + max2; dp[u] = a[u] + max1; ans = max(dp_z[u],ans); ans = max(dp[u],ans);}int main(){ int n; while(cin >> n) { ans = 0; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i <= n - 1; i++) { cin >> u >> v >> w; G[u].push_back(v); G[v].push_back(u); dist[u].push_back(w); dist[v].push_back(w); } dfs(1,-1); cout << ans << endl; } return 0;}
         
        
       
      
     
    
   

转载地址：http://qnwtb.baihongyu.com/