fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/algorithm>
  3. #include <ext/numeric>
  4.  
  5. using namespace std;
  6. using namespace __gnu_cxx;
  7.  
  8. #define endl '\n'
  9.  
  10. int main()
  11. {
  12. #ifdef HOME
  13. 	assert(freopen("input.in", "r", stdin));
  14. 	// assert(freopen("output.out", "w", stdout));
  15. #endif
  16.  
  17. 	ios_base::sync_with_stdio(0);
  18. 	cin.tie(0);
  19.  
  20. 	for (int n; cin >> n;)
  21. 	{
  22. 		vector<vector<int>> tree(n);
  23.  
  24. 		for (int i = 1; i < n; ++i)
  25. 		{
  26. 			int u, v;
  27. 			cin >> u >> v;
  28.  
  29. 			tree[--u].push_back(--v);
  30. 			tree[v].push_back(u);
  31. 		}
  32.  
  33. 		if (n == 2)
  34. 		{
  35. 			cout << "1\n1 2\n";
  36. 			continue;
  37. 		}
  38.  
  39. 		vector<int> size(n), mx(n), leaves;
  40.  
  41. 		function<int(int, int)> dfs = [&](int u, int p)
  42. 		{
  43. 			size[u] = mx[u] = (tree[u].size() == 1);
  44.  
  45. 			for (int v : tree[u]) if (v != p)
  46. 			{
  47. 				size[u] += dfs(v, u);
  48. 				mx[u] = max(mx[u], size[v]);
  49. 			}
  50.  
  51. 			if (tree[u].size() == 1)
  52. 				leaves.push_back(u);
  53.  
  54. 			return size[u];
  55. 		};
  56.  
  57. 		dfs(0, 0);
  58.  
  59. 		for (int u = 0; u < n; ++u)
  60. 			if (2 * max(mx[u], (int) leaves.size() - size[u]) < leaves.size())
  61. 			{
  62. 				leaves.clear();
  63. 				dfs(u, u);
  64. 				break;
  65. 			}
  66.  
  67. 		cout << (leaves.size() + 1) / 2 << endl;
  68.  
  69. 		for (int i = 0, s = (leaves.size() + 1) / 2; i < s; ++i)
  70. 			cout << leaves[i] + 1 << " " << leaves[(i + s) % leaves.size()] + 1 << endl;
  71. 	}
  72.  
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
5
1 2
2 3
3 4
3 5
4
1 2
1 3
1 4
stdout
copy 
2
1 5
4 1
2
2 4
3 2
https://ideone.com/leWJDC
language:
C++14 (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!