fork(1) 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. 	ios::sync_with_stdio(0);   
  34.     cin.tie(0);
  35.     #ifndef ONLINE_JUDGE   
  36.     freopen("input.txt", "r", stdin);   
  37.     freopen("output.txt", "w", stdout);   
  38.     #endif
  39.  
  40.  
  41.  
  42. 	int t,a,b,c;
  43. 	cin>>t;
  44. 	ll ans[t];
  45.  
  46. 	for(int tt=0; tt<t; tt++)
  47. 	{
  48. 		cin>>n;
  49. 		adj.clear();
  50. 		adj.reserve(n);
  51. 		for(int i=0; i<n-1; i++)
  52. 		{
  53. 			cin>>a;
  54. 			cin>>b;
  55. 			cin>>c;
  56.  
  57. 			a--;
  58. 			b--;
  59.  
  60. 			adj[a].push_back(make_pair(b, c));
  61. 			adj[b].push_back(make_pair(a, c));
  62.  
  63. 		}
  64.  
  65. 		int number[n];
  66. 		memset(number,0,sizeof(number));
  67.  
  68. 		finans = 0;
  69. 		dfs(0,-1,number);
  70. 		ans[tt] = finans;
  71. 		cout<<"Case #"<<(tt+1)<<": "<<ans[tt]<<endl;
  72. 	}
  73. 	// for(int tt=1; tt<=t; tt++)
  74. 	// {
  75. 	// 	cout<<"case #"<<tt<<": "<<ans[tt-1]<<endl;
  76. 	// }
  77. 	return 0;
  78. }
  79.  
  80.  
Success #stdin #stdout 0s 4380KB
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/QdTeSF
language:
C++14 (gcc 8.3)
created:
4 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!