fork download
  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 insert_tree(int x)
  23. {
  24. s1.insert(s[x]);
  25. for (auto y : e[x]) if (y != fa[x]) insert_tree(y);
  26. }
  27. void work_sep(int x)
  28. {
  29. if (!s1.empty())
  30. {
  31. int u = s[x], v, w;
  32. int v1 = *(--s1.upper_bound((n - s[x]) / 2));
  33. int v2 = *s1.lower_bound((n - s[x] + 1) / 2);
  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. cout << x << " | ";
  38. for (auto temp : s1) cout << temp << " ";
  39. cout << endl;
  40. ans = min(ans, calc(u, v, w));
  41. cout << "/" << u << " " << v << " " << w << endl;
  42. }
  43. for (auto y : e[x])
  44. {
  45. if (y != fa[x])
  46. {
  47. work_sep(y);
  48. insert_tree(y);
  49. }
  50. }
  51. }
  52. void work_anc(int x)
  53. {
  54. if (!s2.empty())
  55. {
  56. int u = s[x], v, w;
  57. int v1 = *(--s2.upper_bound((n - s[x]) / 2 + s[x]));
  58. int v2 = *s2.lower_bound((n - s[x] + 1) / 2 + s[x]);
  59. if (v1 == 0) v1 = 2e9;
  60. if (v2 == 0) v2 = 2e9;
  61. if (abs(2 * v1 - n - s[x]) < abs(2 * v2 - n - s[x])) v = v1 - u;
  62. else v = v2 - u;
  63. w = n - u - v;
  64. // cout << x << " | " << u << " " << v << " " << w << endl;
  65. ans = min(ans, calc(u, v, w));
  66. }
  67. s2.insert(s[x]);
  68. for (auto y : e[x]) if (y != fa[x]) work_anc(y);
  69. s2.erase(s2.find(s[x]));
  70. }
  71. int main()
  72. {
  73. cin >> n;
  74. for (int x, y, i = 1; i < n; i++)
  75. {
  76. cin >> x >> y;
  77. e[x].push_back(y); e[y].push_back(x);
  78. }
  79. find_fa(1, 0);
  80. find_size(1);
  81. work_sep(1);
  82. work_anc(1);
  83. cout << ans;
  84. return 0;
  85. }
Success #stdin #stdout 0.01s 8240KB
stdin
9
1 3
2 3
3 4
3 5
5 6
5 7
7 8
7 9
stdout
4 | 1 
/1 1 7
5 | 1 1 
/5 2 2
6 | 1 1 
/1 2 6
7 | 1 1 1 
/3 3 3
8 | 1 1 1 
/1 3 5
9 | 1 1 1 1 
/1 4 4
0