91562024-02-16 15:23:31111Hosszú Láncokcpp17Wrong answer 10/10072ms16124 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	vector<vector<int>> g(N + 1);
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	auto dfs = [&](auto dfs, int i) -> void {
		for (int j : g[i]) {
			g[j].erase(find(g[j].begin(), g[j].end(), i));
			dfs(dfs, j);
		}
	};
	dfs(dfs, 1);
	int l = 2, h = N;
	while (l != h) {
		int m = (l + h) / 2;
		auto dfs = [&](auto dfs, int i) -> int {
			multiset<int> s;
			int c = 0;
			for (int j : g[i]) {
				int r = dfs(dfs, j);
				if (r == -1) {
					return -1;
				}
				if (r + 1 == m) {
					c++;
				}
				else {
					s.insert(r);
				}
			}
			vector<int> v;
			while (!s.empty()) {
				int x = *s.begin();
				s.erase(s.begin());
				auto t = s.lower_bound(m - x - 2);
				if (t == s.end()) {
					if (v.size() >= 1 && c > 0) {
						c--;
					}
					else {
						v.push_back(x);
					}
					continue;
				}
				s.erase(t);
			}
			if (v.size() >= 2) {
				return -1;
			}
			if (c >= 2) {
				return m;
			}
			if (v.size() == 1) {
				return i == 1 && c == 1 ? 0 : v[0] + 1;
			}
			return c > 0 ? m : 0;
		};
		int ans = dfs(dfs, 1);
		if (ans == -1 || ans > 0 && ans < m) {
			h = m;
		}
		else {
			l = m + 1;
		}
	}
	cout << l - 1 << '\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1832 KiB
2Accepted3ms2060 KiB
3Accepted3ms2104 KiB
4Accepted3ms2236 KiB
subtask210/10
5Accepted3ms2452 KiB
6Accepted3ms2672 KiB
7Accepted3ms2868 KiB
8Accepted3ms3076 KiB
9Accepted3ms3292 KiB
10Accepted3ms3640 KiB
11Accepted3ms3636 KiB
12Accepted3ms3640 KiB
13Accepted3ms3732 KiB
14Accepted3ms3864 KiB
15Accepted3ms3744 KiB
subtask30/20
16Accepted3ms3868 KiB
17Accepted3ms3972 KiB
18Accepted3ms3968 KiB
19Accepted3ms4192 KiB
20Accepted3ms4176 KiB
21Accepted3ms4180 KiB
22Wrong answer3ms4404 KiB
23Wrong answer3ms4508 KiB
subtask40/20
24Accepted3ms4348 KiB
25Accepted3ms4368 KiB
26Accepted3ms4392 KiB
27Wrong answer3ms4380 KiB
28Wrong answer3ms4264 KiB
29Wrong answer3ms4388 KiB
30Wrong answer3ms4480 KiB
31Wrong answer3ms4500 KiB
subtask50/50
32Wrong answer7ms5468 KiB
33Accepted13ms6504 KiB
34Accepted30ms10272 KiB
35Accepted59ms16124 KiB
36Wrong answer10ms5592 KiB
37Wrong answer20ms6632 KiB
38Wrong answer46ms10400 KiB
39Wrong answer72ms16124 KiB