91572024-02-16 15:28:27111Hosszú Láncokcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva3ms2052 KiB
3Elfogadva3ms2232 KiB
4Elfogadva3ms2444 KiB
subtask210/10
5Elfogadva3ms2656 KiB
6Elfogadva3ms2868 KiB
7Elfogadva3ms2952 KiB
8Elfogadva2ms2952 KiB
9Elfogadva2ms2948 KiB
10Elfogadva2ms2948 KiB
11Elfogadva3ms3100 KiB
12Elfogadva3ms3148 KiB
13Elfogadva3ms3284 KiB
14Elfogadva3ms3260 KiB
15Elfogadva3ms3268 KiB
subtask320/20
16Elfogadva3ms3364 KiB
17Elfogadva3ms3360 KiB
18Elfogadva3ms3264 KiB
19Elfogadva3ms3396 KiB
20Elfogadva3ms3600 KiB
21Elfogadva3ms3940 KiB
22Elfogadva3ms3940 KiB
23Elfogadva3ms3848 KiB
subtask420/20
24Elfogadva3ms3836 KiB
25Elfogadva3ms3916 KiB
26Elfogadva3ms4032 KiB
27Elfogadva3ms4320 KiB
28Elfogadva3ms4344 KiB
29Elfogadva3ms4428 KiB
30Elfogadva3ms4532 KiB
31Elfogadva3ms4836 KiB
subtask550/50
32Elfogadva7ms6004 KiB
33Elfogadva13ms7032 KiB
34Elfogadva28ms10772 KiB
35Elfogadva59ms16736 KiB
36Elfogadva9ms5972 KiB
37Elfogadva19ms7132 KiB
38Elfogadva64ms10900 KiB
39Elfogadva119ms16748 KiB