fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. 	int *size;
  6. 	map<int, vector<int>> t;
  7. 	int n; 
  8.  
  9. 	void dfs(int u, int p) {
  10. 		size[u] = 0;
  11. 		for(auto v : t[u]) {
  12.  
  13. 			if(v == p) continue;
  14. 			dfs(v, u);
  15. 			size[u] += size[v] + 1;
  16. 		}
  17. 	}
  18.  
  19. int main() {
  20. 			cin >> n;
  21.  
  22. 		for(int i = 0; i < n-1; i++) {
  23. 			int u, v;
  24. 			cin >> u >> v;
  25. 			t[u].push_back(v);
  26. 			t[v].push_back(u);
  27. 		}
  28. 		size = new int[n+1];
  29. 		int node = -1; 
  30. 		int node_val = INT_MAX;
  31.  
  32. 		for(int i = 1; i <= n; i++) {
  33. 			int t_size = 0;
  34.  
  35. 			// for(int i = 0; i <= n; i++) size[i] = 0;
  36. 			dfs(i, -1);
  37.  
  38. 			for(int i = 1; i <= n; i++) {
  39. 				t_size += size[i];
  40.  
  41. 			}
  42. 			if(node_val > t_size) {
  43. 				node_val = t_size;
  44. 				node = i;
  45. 			}
  46. 			else if(node_val == t_size && (node > i)) node = i;
  47.  
  48. 			// for(int i = 1; i <= n; i++) cout << size[i];
  49. 			// cout << '\n';
  50. 		}
  51. 		// for(auto x:t) {
  52. 		// 	cout << x.first << ":";
  53. 		// 	for(auto xx : t[x.first])
  54. 		// 		cout<< xx << " "; 
  55. 		// 	cout << "\n";	
  56. 		// }
  57. 		cout << node;
  58. 	return 0;
  59. }
Success #stdin #stdout 0s 4540KB
comments (?)
stdin
copy 
4
1 2
2 3
3 4
stdout
copy 
2
https://ideone.com/gxnkXd
language:
C++14 (gcc 8.3)
created:
4 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!