Submission #1363232

#TimeUsernameProblemLanguageResultExecution timeMemory
1363232NikoBaoticTorrent (COI16_torrent)C++20
100 / 100
218 ms29920 KiB
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 3e5 + 10;

int n, x, y;
vector<int> adj[N];
int par[N];
map<pii, ll> c;

void dfs(int node) {
	for (int u : adj[node]) {
		if (u == par[node]) continue;
		par[u] = node;
		dfs(u);
	}
}

ll comp(ll node, int s, int prev = 0) {
	if (prev == 0 and c.find({node, s}) != c.end()) return c[{node, s}];
	vector<ll> se;

	for (int u : adj[node]) {
		if (u == prev or u == s) continue;
		se.pb(comp(u, s, node));
	}

	sort(all(se));
	reverse(all(se));

	ll ans = 0;

	for (int i = 0; i < sz(se); i++) {
		ans = max(ans, i + 1 + se[i]);
	}

	if (prev == 0) c[{node, s}] = ans;

	return ans;
}

int main() {
	FIO;
	
	cin >> n >> x >> y;

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	dfs(x);

	vector<int> p;

	int cur = y;
	while (cur != x) {
		p.pb(cur);
		cur = par[cur];
	}
	p.pb(x);

	int l = 0;
	int r = sz(p) - 2;
	ll ans = 1e18;

	if (n > 1e3) {
		while (l + 2 < r) {
			int mid1 = l + (r - l + 1) / 3;
			int mid2 = l + (r - l + 1) / 3 * 2;

			ll v1 = max(comp(y, p[mid1 + 1]), comp(x, p[mid1]));
			ll v2 = max(comp(y, p[mid2 + 1]), comp(x, p[mid2]));
			ll vl = max(comp(y, p[l + 1]), comp(x, p[l]));
			ll vr = max(comp(y, p[r + 1]), comp(x, p[r]));

			if (vl >= v1 and v2 <= vr) {
				l = mid1;
				r = mid2;
			} else if (v1 > v2) {
				l = mid1;
			} else {
				r = mid2;
			}
		}
	}
	
	for (int i = l; i <= r; i++) {
		ans = min(ans, max(comp(y, p[i + 1]), comp(x, p[i])));
	}

	cout << ans << "\n";

	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...