fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. vector<pair<int, ll> > miti[1111111];
  11.  
  12. void dfs(int n, int o, ll k, ll* d){
  13. 	d[n] = k;
  14. 	int l = miti[n].size();
  15. 	for (int i = 0; i < l; i++){
  16. 		if (miti[n][i].first != o){
  17. 			dfs(miti[n][i].first, n, k + miti[n][i].second, d);
  18. 		}
  19. 	}
  20. }
  21.  
  22. ll d1[1111111];
  23. ll d2[1111111];
  24.  
  25. int main(){
  26. 	int n;
  27. 	scanf("%d", &n);
  28. 	for (int i = 0; i < n - 1; i++){
  29. 		int a, b;
  30. 		ll c;
  31. 		scanf("%d%d%lld", &a, &b, &c);
  32. 		miti[a].push_back(make_pair(b, c));
  33. 		miti[b].push_back(make_pair(a, c));
  34. 	}
  35. 	dfs(1, -1, 0, d1);
  36. 	ll mw = -1;
  37. 	int ab = -1;
  38. 	for (int i = 1; i <= n; i++){
  39. 		if (mw < d1[i]){
  40. 			mw = d1[i];
  41. 			ab = i;
  42. 		}
  43. 	}
  44. 	dfs(ab, -1, 0, d1);
  45. 	mw = -1;
  46. 	int bb = -1;
  47. 	for (int i = 1; i <= n; i++){
  48. 		if (mw < d1[i]){
  49. 			mw = d1[i];
  50. 			bb = i;
  51. 		}
  52. 	}
  53. 	dfs(bb, -1, 0, d2);
  54. 	for (int i = 1; i <= n; i++){
  55. 		if (d1[i] == d2[i]) printf("%d\n", min(ab, bb));
  56. 		else if (d1[i] > d2[i]) printf("%d\n", ab);
  57. 		else printf("%d\n", bb);
  58. 	}
  59. 	return 0;
  60. }
  61.  
Success #stdin #stdout 0.01s 33800KB
comments (?)
stdin
copy 
3
1 2 10
2 3 15
stdout
copy 
3
3
1
https://ideone.com/5GXlvC
language:
C++ (gcc 8.3)
created:
8 years 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!