fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. vector<int>sum(100000001);
  7.  
  8. void dfs(int node,vector<vector<int>>graph,vector<bool>&visited,vector<int>&parent,vector<int>value){
  9. 	visited[node]=true;
  10.  
  11. 	for(auto it:graph[node]){
  12. 		if(!visited[it]){
  13. 			dfs(it,graph,visited,parent,value);
  14. 			parent[it]=node;
  15. 		}
  16. 	}
  17.  
  18. 	int s=0;
  19. 	for(auto it:graph[node]){
  20. 		if(it==parent[node]){
  21. 			//nothing 
  22. 		}
  23.  
  24. 		else{
  25. 			s=max(s,sum[it]);
  26. 		}
  27. 	}
  28.  
  29. 	sum[node]=value[node]+s;
  30.  
  31. }
  32. int main(){
  33. 	int n;
  34. 	cin>>n;
  35.  
  36. 	vector<vector<int>>graph(n);
  37. 	int m=n-1;
  38.  
  39. 	int i=1;
  40. 	while(i<=m){
  41. 		int x,y;
  42. 		cin>>x>>y;
  43. 		x--,y--;
  44.  
  45. 		graph[x].push_back(y);
  46. 		graph[y].push_back(x);
  47.  
  48. 		i++;
  49. 	}
  50.  
  51. 	vector<int>value(n);
  52.  
  53. 	for(int i=0;i<n;i++){
  54. 		cin>>value[i];
  55. 	}
  56.  
  57. 	vector<bool>visited(n,false);
  58. 	vector<int>parent(n,-1);
  59.  
  60. 	dfs(0,graph,visited,parent,value);
  61.  
  62. 	int answer=INT_MIN;
  63. 	for(int i=0;i<n;i++){
  64. 		cout<<"Sum of subtree rooted at "<<i+1<<" : "<<sum[i]<<endl;
  65. 		answer=max(answer,sum[i]);
  66. 	}
  67.  
  68. 	cout<<"Max sum : "<<answer<<endl;
  69. 	return 0;
  70. }
Success #stdin #stdout 0.09s 393716KB
comments (?)
stdin
copy 
5
1 2
2 3 
3 4 
1 5 
5 7 -10 4 15
stdout
copy 
Sum of subtree rooted at 1 : 20
Sum of subtree rooted at 2 : 7
Sum of subtree rooted at 3 : -6
Sum of subtree rooted at 4 : 4
Sum of subtree rooted at 5 : 15
Max sum : 20
https://ideone.com/omfzR8
language:
C++ (gcc 8.3)
created:
3 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!