fork download
copy 
  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
comments (?)
stdin
copy 
8
1 2
1 3
1 4
4 5
1 6
6 7
7 8
stdout
copy 
3
https://ideone.com/q2mbJR
language:
C++14 (gcc 8.3)
created:
5 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!