91572024-02-16 15:28:27111Hosszú Láncokcpp17Accepted 100/100119ms16748 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
1Accepted3ms1828 KiB
2Accepted3ms2052 KiB
3Accepted3ms2232 KiB
4Accepted3ms2444 KiB
subtask210/10
5Accepted3ms2656 KiB
6Accepted3ms2868 KiB
7Accepted3ms2952 KiB
8Accepted2ms2952 KiB
9Accepted2ms2948 KiB
10Accepted2ms2948 KiB
11Accepted3ms3100 KiB
12Accepted3ms3148 KiB
13Accepted3ms3284 KiB
14Accepted3ms3260 KiB
15Accepted3ms3268 KiB
subtask320/20
16Accepted3ms3364 KiB
17Accepted3ms3360 KiB
18Accepted3ms3264 KiB
19Accepted3ms3396 KiB
20Accepted3ms3600 KiB
21Accepted3ms3940 KiB
22Accepted3ms3940 KiB
23Accepted3ms3848 KiB
subtask420/20
24Accepted3ms3836 KiB
25Accepted3ms3916 KiB
26Accepted3ms4032 KiB
27Accepted3ms4320 KiB
28Accepted3ms4344 KiB
29Accepted3ms4428 KiB
30Accepted3ms4532 KiB
31Accepted3ms4836 KiB
subtask550/50
32Accepted7ms6004 KiB
33Accepted13ms7032 KiB
34Accepted28ms10772 KiB
35Accepted59ms16736 KiB
36Accepted9ms5972 KiB
37Accepted19ms7132 KiB
38Accepted64ms10900 KiB
39Accepted119ms16748 KiB