fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, ans = 2e9;
  4. vector <int> e[200010];
  5. int fa[200010], s[200010];
  6. int calc(int u, int v, int w)
  7. {
  8. 	return max(max(u, v), w) - min(min(u, v), w);
  9. }
  10. void find_fa(int y, int x)
  11. {
  12. 	fa[y] = x;
  13. 	for (auto z : e[y]) if (z != x) find_fa(z, y);
  14. }
  15. void find_size(int x)
  16. {
  17. 	for (auto y : e[x]) if (y != fa[x])	find_size(y);
  18. 	s[x] = 1;
  19. 	for (auto y : e[x]) if (y != fa[x]) s[x] += s[y];
  20. }
  21. multiset <int> s1, s2;
  22. void work_sep(int x)
  23. {
  24. 	if (!s1.empty())
  25. 	{
  26. 		int u = s[x], v, w;
  27. 		int v1, v2;
  28. 		set <int> :: iterator it1 = s1.upper_bound((n - s[x]) / 2);
  29. 		if (it1 == s1.begin()) v1 = 2e9;
  30. 		else v1 = *(--it1);
  31. 		set <int> :: iterator it2 = s1.lower_bound((n - s[x] + 1) / 2);
  32. 		if (it2 == s1.end()) v2 = 2e9;
  33. 		else v2 = *it2;
  34. 		if (abs(2 * v1 - n + s[x]) < abs(2 * v2 - n + s[x])) v = v1;
  35. 		else v = v2;
  36. 		w = n - u - v;
  37. 		ans = min(ans, calc(u, v, w));
  38. 	}
  39. 	for (auto y : e[x])
  40. 	{
  41. 		if (y != fa[x])
  42. 		{
  43. 			work_sep(y);
  44.  
  45. 		}
  46. 	}
  47.     s1.insert(x);
  48. }
  49. void work_anc(int x)
  50. {
  51. 	if (!s2.empty())
  52. 	{
  53. 		int u = s[x], v, w;
  54. 		int v1, v2;
  55. 		set <int> :: iterator it1 = s2.upper_bound((n - s[x]) / 2 + s[x]);
  56. 		if (it1 == s2.begin()) v1 = 2e9;
  57. 		else v1 = *(--it1);
  58. 		set <int> :: iterator it2 = s2.lower_bound((n - s[x] + 1) / 2 + s[x]);
  59. 		if (it2 == s2.end()) v2 = 2e9;
  60. 		else v2 = *it2;
  61.  
  62. 		if (abs(2 * v1 - n - s[x]) < abs(2 * v2 - n - s[x])) v = v1 - u;
  63. 		else v = v2 - u;
  64. 		w = n - u - v;
  65. 		// cout << x << " | " << u << " " << v << " " << w << endl;
  66. 		ans = min(ans, calc(u, v, w));
  67. 	}
  68. 	s2.insert(s[x]);
  69. 	for (auto y : e[x]) if (y != fa[x]) work_anc(y);
  70. 	s2.erase(s2.find(s[x]));
  71. }
  72. int main()
  73. {
  74. 	ios::sync_with_stdio(0);
  75.     cin.tie(0) , cout.tie(0);
  76. 	cin >> n;
  77. 	for (int x, y, i = 1; i < n; i++)
  78. 	{
  79. 		cin >> x >> y;
  80. 		e[x].push_back(y); e[y].push_back(x);
  81. 	}
  82. 	find_fa(1, 0);
  83. 	find_size(1);
  84. 	work_sep(1);
  85. 	work_anc(1);
  86. 	cout << ans;
  87. 	return 0;
  88. }
Success #stdin #stdout 0.01s 8444KB
comments (?)
stdin
copy 
6
1 2
1 3
3 4
3 5
5 6
stdout
copy 
Standard output is empty
https://ideone.com/2wBupy
language:
C++14 (gcc 8.3)
created:
5 days 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!