Submission #1358152

#TimeUsernameProblemLanguageResultExecution timeMemory
1358152MinbaevTorrent (COI16_torrent)C++20
100 / 100
1052 ms44904 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long

const int inf = 1e18;
const int mod = 998244353;

void solve(){
	
	int n, a, b;
	cin >> n >> a >> b;
	a -= 1;
	b -= 1;
	vector<vector<pair<int,int>>>g(n);
	vector<pair<int,int>>vs;
	
	for(int i = 0;i<n-1;i++){
		int x, y;
		cin >> x >> y;
		x -= 1;
		y -= 1;
		g[x].push_back({y, i});
		g[y].push_back({x, i});
		vs.push_back({x, y});
	}
	
	vector<int>p(n), u, op(n);
	
	auto dfs = [&](auto self, int x, int pr) -> void {
		for(auto [to, ind] : g[x]){
			if(to == pr)continue;
			p[to] = x; op[to] = ind;
			self(self, to, x);
		}
	};
	
	dfs(dfs, a, -1);
	int uio = b;
	while(uio != a){
		u.push_back(op[uio]);
		uio = p[uio];
	}
	//~ cout << ";;;;\n";
	//~ for(int i = 0;i<n;i++){
		//~ cout << p[i] << " " << op[i] << "\n";
	//~ }
	
	vector<int>vis(n + 5), dp(n + 5);
	
	auto ans = [&](auto self, int x, int pr) -> void {
		dp[x] = 0;
		vector<int>io;
		for(auto [to, ind] : g[x]){
			if(to == pr || vis[ind])continue;
			self(self, to, x);
			io.push_back(dp[to]);
		}
		sort(io.begin(), io.end());
		reverse(io.begin(), io.end());
		int mx = 0;
		for(int i = 0;i<io.size();i++){
			mx = max(mx, io[i] + i + 1);
		}
		dp[x] = mx;
	};
	
	auto f = [&](int ind) -> int {
		vis[ind] = 1;
		ans(ans, a, -1);
		//~ for(int i = 0;i<n;i++)cout << dp[i] << " ";
		//~ cout << "\n";
		ans(ans, b, -1);
		//~ for(int i = 0;i<n;i++)cout << dp[i] << " ";
		//~ cout << "\n";
		vis[ind] = 0;
		return max(dp[a], dp[b]);
	};
		
	int l = 0, r = u.size() - 1, res = -1;
	while(r-l >= 75){
		int l1 = l + (r-l) / 3;
		int r1 = r - (r-l) / 3;
		
		int val1 = f(u[l1]);
		int val2 = f(u[r1]);
		
		if(val1 > val2){
			l = l1;
		}
		else r = r1;
	}
	
	res = inf;
	for(int i = l;i<=r;i++){
		int val = f(u[i]);
		res = min(res, val);
	}
	
	cout << res << "\n";
	
}
/*
17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2
//
10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10
//
6 2 1
1 2
2 3
2 4
1 5
5 6
*/
 signed main()
{
  //~ freopen("cbarn2.in", "r", stdin);
  //~ freopen("cbarn2.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1;
    //cin >> tt;
    while(tt--)solve();    
 
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...