fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll ; 
  4. ll sum[100];
  5. int b[100];
  6. void DFS(int node,vector <int> G[],int used[],int parent[]){
  7.  
  8.     used[node] = 1 ; 
  9.  
  10.     for(auto u: G[node]){ //iterating all children "u" of "node"
  11.  
  12.         if(used[u]==0){
  13.             //if this node/branch has never been visited before 
  14.             //just go into it and search it using dfs in recursion
  15.             parent[u] = node ; 
  16.             DFS(u,G,used,parent);
  17.  
  18.         }
  19.     }
  20.  
  21.  
  22.     //print(node)--->parent
  23.     //----> bottom up traversal 
  24.     ll s = 0 ; 
  25.     for(auto child: G[node]){
  26.  
  27.         if(child==parent[node]){
  28.             //it means the child node is parent of the node
  29.             //it is not the child
  30.             //ignore it
  31.         }
  32.  
  33.         else{
  34.             s = max(s, sum[child]); 
  35.         }
  36.     }
  37.  
  38.     sum[node] = b[node] + s; 
  39.  
  40.  
  41. }
  42.  
  43. int main(){
  44.     int n ; 
  45.     cin>>n ; 
  46.     vector <int> G[n+1];
  47.     int i = 1 ; 
  48.     while(i<=n){
  49.         cin>>b[i] ; 
  50.         i++;
  51.     }
  52.  
  53.     i = 1 ; 
  54.     while(i<=n-1){
  55.         int u,v;
  56.         cin>>u>>v ; 
  57.         G[u].push_back(v);
  58.         G[v].push_back(u); 
  59.         i++;
  60.     }
  61.     int used[n+1] = {0};
  62.     int parent[n+1] = {0};
  63.     DFS(1,G,used,parent); //starts from node 1  
  64.  
  65.     ll answer = -100000000000000;    
  66.     i = 1 ;
  67.     while(i<=n){
  68.         answer=max(answer,sum[i]);
  69.         i++;
  70.     }
  71.     cout<<(answer); 
  72.     return 0 ; 
  73. }
  74.  
  75.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
5
5 7 -10 4 15 
1 2
2 3 
3 4 
1 5
stdout
copy 
20
https://ideone.com/8WjdGb
language:
C++ (gcc 8.3)
created:
6 days 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!