fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1.1e5;
  5. int N;
  6. vector<int> adj[MAXN];
  7. vector<int> order;
  8.  
  9. void dfs(int cur, int prv) {
  10. if (prv != -1) {
  11. adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv));
  12. }
  13. for (int nxt : adj[cur]) {
  14. dfs(nxt, cur);
  15. }
  16. order.push_back(cur);
  17. }
  18.  
  19. int bestUp[MAXN];
  20.  
  21. bool isGood(int v) {
  22. auto pairUp = [&](const vector<int>& vals) -> bool {
  23. int i = 0, j = int(lower_bound(vals.begin(), vals.end(), v) - vals.begin());
  24. int extraCnt = int(vals.size()) - j;
  25. j--;
  26. for (; i <= j; i++) {
  27. if (i < j && vals[i]+vals[j] >= v) {
  28. j--;
  29. } else {
  30. if (extraCnt == 0) return false;
  31. extraCnt--;
  32. }
  33. }
  34. return true;
  35. };
  36. for (int cur : order) {
  37. vector<int> ch; ch.reserve(adj[cur].size());
  38. for (int nxt : adj[cur]) {
  39. ch.push_back(bestUp[nxt]+1);
  40. }
  41. sort(ch.begin(), ch.end());
  42.  
  43. if (cur == 0) {
  44. return pairUp(ch);
  45. }
  46.  
  47. int mi = -1, ma = int(ch.size());
  48. while (ma - mi > 1) {
  49. int md = (mi + ma) / 2;
  50. vector<int> nch = ch;
  51. nch.erase(nch.begin()+md);
  52. if (pairUp(nch)) {
  53. mi = md;
  54. } else {
  55. ma = md;
  56. }
  57. }
  58. if (mi >= 0) {
  59. bestUp[cur] = ch[mi];
  60. } else if (pairUp(ch)) {
  61. bestUp[cur] = 0;
  62. } else {
  63. return false;
  64. }
  65. }
  66. assert(false);
  67. }
  68.  
  69. int main() {
  70. ios_base::sync_with_stdio(0); cin.tie(0);
  71.  
  72. cin >> N;
  73. for (int e = 0; e < N-1; e++) {
  74. int a, b; cin >> a >> b; a--, b--;
  75. adj[a].push_back(b);
  76. adj[b].push_back(a);
  77. }
  78.  
  79. order.reserve(N);
  80. dfs(0, -1);
  81.  
  82. int mi = 1, ma = N;
  83. while (ma - mi > 1) {
  84. int md = (mi + ma) / 2;
  85. if (isGood(md)) {
  86. mi = md;
  87. } else {
  88. ma = md;
  89. }
  90. }
  91. cout << mi << '\n';
  92.  
  93. return 0;
  94. }
  95.  
Success #stdin #stdout 0s 6068KB
stdin
8
1 2
1 3
1 4
4 5
1 6
6 7
7 8
stdout
3