fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e5 + 5;
  5.  
  6. long long n,ans, a[MaxN], dp[MaxN];
  7. vector<long long> vt[MaxN];
  8.  
  9. void dfs(long long u, long long par)
  10. {
  11.     dp[u]=a[u];
  12.  
  13.     long long mx1=LLONG_MIN;
  14.     long long mx2=LLONG_MIN;
  15.  
  16.     for (long long v : vt[u])
  17.     {
  18.         if(v==par) continue;
  19.  
  20.         dfs(v,u);
  21.  
  22.         if(dp[v]>mx1)
  23.         {
  24.             mx2=mx1;
  25.             mx1=dp[v];
  26.         }
  27.         else if(dp[v]>mx2)
  28.         {
  29.             mx2=dp[v];
  30.         }
  31.     }
  32.  
  33.     dp[u]+=max(0LL,mx1);
  34.  
  35.     long long cur=a[u]+max(0LL,mx1)+max(0LL,mx2);
  36.  
  37.     ans=max(ans,cur);
  38. }
  39.  
  40. void input()
  41. {
  42.     cin >> n;
  43.  
  44.     for (long long i=1; i<=n; i++)
  45.     {
  46.         cin >> a[i];
  47.     }
  48.  
  49.     for (long long i=1; i<n; i++)
  50.     {
  51.         long long u,v;
  52.         cin >> u >> v;
  53.  
  54.         vt[u].push_back(v);
  55.         vt[v].push_back(u);
  56.     }
  57. }
  58.  
  59. void solve()
  60. {
  61.     ans=LLONG_MIN;
  62.  
  63.     dfs(1,-1);
  64.  
  65.     cout << ans << "\n";
  66. }
  67.  
  68. int main()
  69. {
  70.     ios_base::sync_with_stdio(0);
  71.     cin.tie(0);
  72.  
  73.     input();
  74.     solve();
  75. }
Success #stdin #stdout 0.01s 6596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/zg3oLO
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!