fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define ll long long
  6. #define mod 1000000000
  7.  
  8. int n;
  9. ll finans;
  10. vector<vector<pair<int, int>>>adj;
  11.  
  12. void dfs(int src, int par, int number[])
  13. {
  14. 	number[src] = 1;
  15. 	for(auto it:adj[src])
  16. 	{
  17. 		if( it.first != par )
  18. 		{
  19. 			dfs(it.first, src, number);
  20. 			number[src] += number[it.first];
  21. 			// cout<<it.first<<"	"<<src<<"	"<<number[it.first]<<"	"<<(n-number[it.first])<<endl;
  22.  
  23. 			ll curr = (  min( number[it.first], n-number[it.first] ) * 2ll * it.second );
  24.  
  25. 			finans += curr;
  26. 		}
  27. 	}
  28. }
  29.  
  30.  
  31. int main()
  32. {
  33. 	#ifndef ONLINE_JUDGE
  34. 	freopen("input.txt","r",stdin);
  35. 	freopen("output.txt","w",stdout);
  36. 	#endif
  37.  
  38.  
  39. 	int t,a,b,c;
  40. 	cin>>t;
  41. 	ll ans[t];
  42.  
  43. 	for(int tt=0; tt<t; tt++)
  44. 	{
  45. 		cin>>n;
  46. 		adj.clear();
  47. 		adj.reserve(n);
  48. 		for(int i=0; i<n-1; i++)
  49. 		{
  50. 			cin>>a;
  51. 			cin>>b;
  52. 			cin>>c;
  53.  
  54. 			a--;
  55. 			b--;
  56.  
  57. 			adj[a].push_back(make_pair(b, c));
  58. 			adj[b].push_back(make_pair(a, c));
  59.  
  60. 		}
  61.  
  62. 		int number[n];
  63. 		memset(number,0,sizeof(number));
  64.  
  65. 		finans = 0;
  66. 		dfs(0,-1,number);
  67. 		ans[tt] = finans;
  68. 		cout<<"case #"<<(tt+1)<<": "<<ans[tt]<<endl;
  69. 	}
  70. 	// for(int tt=1; tt<=t; tt++)
  71. 	// {
  72. 	// 	cout<<"case #"<<tt<<": "<<ans[tt-1]<<endl;
  73. 	// }
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
2
4
1 2 3
2 3 2
4 3 2
6
1 2 3
2 3 4
2 4 1
4 5 8
5 6 5
stdout
copy 
case #1: 18
case #2: 62
https://ideone.com/NgpkDC
problem HOLI, based on SPOJ submission 25590696 (CPP14), 2020-03-21 04:40:45
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!