fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5. typedef long long int ll;
  6.  
  7. void dfs(int node , vector<int> g[] , vector<int> &visited , vector<int> &parent,vector<int> &b,vector<int> &sum){
  8. 	visited[node]=1;
  9. 	for(auto it : g[node]){
  10.  
  11. 	if(visited[it]==0){
  12. 		parent[it]=node;
  13. 		dfs(it,g,visited,parent,b,sum);
  14. 	}
  15.  
  16. 	}
  17.  
  18. 	int s=0;
  19. 	for(auto it : g[node]){
  20. 		if(parent[node]!=it){
  21. 			s=max(s,sum[it]);
  22.  
  23. 		}
  24. 	}
  25.  
  26. 	sum[node] = b[node] + s;
  27.  
  28. }
  29.  
  30. int main() {
  31. 	// your code goes here
  32.  
  33. 	int n;
  34. 	cin>>n;
  35. 	vector<int> g[n+1];
  36.  
  37. 		vector<int> b(n+1);
  38. 	for(int i=1;i<=n;i++){
  39. 		cin>>b[i];
  40.  
  41. 	}
  42.  
  43.  
  44. 	for(int i=1;i<=n-1;i++){
  45. 		int u,v;
  46. 		cin>>u>>v;
  47. 		g[u].push_back(v);
  48. 		g[v].push_back(u);
  49.  
  50. 	}
  51.  
  52.  
  53.  
  54. 	vector<int> visited(n+1,0);
  55. 	vector<int> parent(n+1,-1);
  56. 	vector<int> sum(n+1,0);
  57. 	dfs(1,g,visited,parent,b,sum);
  58.  
  59. 	int answer=INT_MIN;
  60. 	for(int i=1;i<=n;i++){
  61. 		answer=max(answer,sum[i]);
  62.  
  63. 	}
  64.  
  65. 	cout<<answer;
  66.  
  67.  
  68. 	return 0;
  69. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
5 7 -10 4 15 
1 2
2 3 
3 4 
1 5
stdout
copy 
20
https://ideone.com/p8gsJ7
language:
C++14 (gcc 8.3)
created:
6 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!