fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5. vector<int>sum(1000001);
  6.  
  7. void dfs(int node,vector<vector<int>>graph,vector<bool>&visited,vector<int>&parent,vector<int>value){
  8. 	visited[node]=true;
  9.  
  10. 	for(auto it:graph[node]){
  11. 		if(!visited[it]){
  12. 			parent[it]=node;
  13. 			dfs(it,graph,visited,parent,value);
  14.  
  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=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.  
  52. 	vector<int>value(n);
  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.  
  61. 	dfs(0,graph,visited,parent,value);
  62.  
  63. 	int answer=INT_MIN;
  64. 	for(int i=0;i<n;i++){
  65. 		cout<<"Sum of subtree rooted at "<<i+1<<" : "<<sum[i]<<endl;
  66. 		answer=max(answer,sum[i]);
  67. 	}
  68.  
  69. 	cout<<"Max sum : "<<answer<<endl;
  70. 	return 0;
  71. }
Success #stdin #stdout 0.01s 6844KB
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 : 21
Sum of subtree rooted at 2 : 1
Sum of subtree rooted at 3 : -6
Sum of subtree rooted at 4 : 4
Sum of subtree rooted at 5 : 15
Max sum : 21
https://ideone.com/TDBGrQ
language:
C++ (gcc 8.3)
created:
9 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!