fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. pair <int, int> g[2010];
  5. int s[2010], fa[2010], f[2010][30];
  6. int dep[2010];
  7. vector <int> e[2010];
  8. void find_fa(int x, int father)
  9. {
  10. 	fa[x] = father;
  11. 	for (auto y : e[x])
  12. 		if (y != father)
  13. 			find_fa(y, x);
  14. }
  15. void find_dep(int x, int depth)
  16. {
  17. 	dep[x] = depth;
  18. 	for (auto y : e[x])
  19. 		if (y != fa[x])
  20. 			find_dep(y, depth + 1);
  21. }
  22. void find_size(int x)
  23. {
  24. 	for (auto y : e[x])
  25. 		if (y != fa[x])
  26. 			find_size(y);
  27. 	for (auto y : e[x])
  28. 		if (y != fa[x])
  29. 			s[x] += s[y];
  30. 	s[x] += 1;
  31. }
  32. bool checkdot(int x, int y)
  33. {
  34. 	int dis = dep[y] - dep[x];
  35. 	int cnt = 0, ts = y;
  36. 	while (dis > 0)
  37. 	{
  38. 		if (dis % 2 == 1)
  39. 			ts = f[ts][cnt];
  40. 		cnt++;
  41. 		dis /= 2;
  42. 	}
  43. 	if (ts == x)
  44. 		return 1;
  45. 	return 0;
  46. }
  47. bool checkline(int id1, int id2)
  48. {
  49. 	if (checkdot(g[id1].second, g[id2].first))
  50. 		return 1;
  51. 	if (checkdot(g[id2].second, g[id1].first))
  52. 		return 1;
  53. 	return 0;
  54. }
  55. int main()
  56. {
  57. 	cin >> n;
  58. 	for (int i = 1; i < n; i++)
  59. 	{
  60. 		int x, y;
  61. 		cin >> x >> y;
  62. 		g[i] = {x, y};
  63. 		e[x].push_back(y);
  64. 		e[y].push_back(x);
  65. 	}
  66. 	find_fa(1, 0);
  67. 	find_dep(1, 1);
  68. 	find_size(1);
  69. 	for (int i = 1; i <= n; i++)
  70. 		if (fa[g[i].second] != g[i].first)
  71. 			swap(g[i].first, g[i].second);
  72. 	for (int i = 1; i <= n; i++)
  73. 		f[i][0] = fa[i];
  74. 	f[1][0] = 1;
  75. 	for (int i = 1; i <= 20; i++)
  76. 		for (int j = 1; j <= n; j++)
  77. 			f[j][i] = f[f[j][i - 1]][i - 1];
  78. 	int ans = 1e9;
  79. 	for (int i = 1; i + 1 < n; i++)
  80. 		for (int j = i + 1; j < n; j++)
  81. 		{
  82. 			bool flag = checkline(i, j);
  83. 			if (flag == 1)
  84. 			{
  85. 				int X = s[g[i].second], Y = s[g[j].second];
  86. 				int x = min(X, Y), y = abs(X - Y), z = n - max(X, Y);
  87. 				ans = min(ans, max(max(x, y), z) - min(min(x, y), z));
  88. 				// cout << x << " " << y << " " << z << endl;
  89. 			}
  90. 			else
  91. 			{
  92. 				int x = s[g[i].second], y = s[g[j].second], z = n - x - y;
  93. 				ans = min(ans, max(max(x, y), z) - min(min(x, y), z));
  94. 			}
  95. 			// cout << ans << " " << i << " " << j << endl;
  96. 		}
  97. 	cout << ans;
  98. 	return 0;
  99. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6
1 2
1 3
3 4
3 5
5 6
stdout
copy 
Standard output is empty
https://ideone.com/8MJ3Kk
language:
C++14 (gcc 8.3)
created:
6 hours 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!