9157 2024. 02. 16 15:28:27 111 Hosszú Láncok cpp17 Elfogadva 100/100 119ms 16748 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 3ms 2052 KiB
3 Elfogadva 3ms 2232 KiB
4 Elfogadva 3ms 2444 KiB
subtask2 10/10
5 Elfogadva 3ms 2656 KiB
6 Elfogadva 3ms 2868 KiB
7 Elfogadva 3ms 2952 KiB
8 Elfogadva 2ms 2952 KiB
9 Elfogadva 2ms 2948 KiB
10 Elfogadva 2ms 2948 KiB
11 Elfogadva 3ms 3100 KiB
12 Elfogadva 3ms 3148 KiB
13 Elfogadva 3ms 3284 KiB
14 Elfogadva 3ms 3260 KiB
15 Elfogadva 3ms 3268 KiB
subtask3 20/20
16 Elfogadva 3ms 3364 KiB
17 Elfogadva 3ms 3360 KiB
18 Elfogadva 3ms 3264 KiB
19 Elfogadva 3ms 3396 KiB
20 Elfogadva 3ms 3600 KiB
21 Elfogadva 3ms 3940 KiB
22 Elfogadva 3ms 3940 KiB
23 Elfogadva 3ms 3848 KiB
subtask4 20/20
24 Elfogadva 3ms 3836 KiB
25 Elfogadva 3ms 3916 KiB
26 Elfogadva 3ms 4032 KiB
27 Elfogadva 3ms 4320 KiB
28 Elfogadva 3ms 4344 KiB
29 Elfogadva 3ms 4428 KiB
30 Elfogadva 3ms 4532 KiB
31 Elfogadva 3ms 4836 KiB
subtask5 50/50
32 Elfogadva 7ms 6004 KiB
33 Elfogadva 13ms 7032 KiB
34 Elfogadva 28ms 10772 KiB
35 Elfogadva 59ms 16736 KiB
36 Elfogadva 9ms 5972 KiB
37 Elfogadva 19ms 7132 KiB
38 Elfogadva 64ms 10900 KiB
39 Elfogadva 119ms 16748 KiB