Submission #1357808

#TimeUsernameProblemLanguageResultExecution timeMemory
1357808MinbaevTorrent (COI16_torrent)C++20
31 / 100
2097 ms39508 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 {
		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;
	};
	
	int res = inf;
	
	for(int i = 0;i<u.size();i++){
		if(i != 0)vis[u[i-1]] = 0;
		vis[u[i]] = 1;
		
		for(int j = 0;j<n;j++)dp[j] = 0;
		
		ans(ans, a, -1);
		
		//~ cout << u[i] << "\n";
		
		//~ for(int j = 0;j<n;j++){
			//~ cout << dp[j] << " ";
		//~ }
		//~ cout << "\n";
		ans(ans, b, -1);
		//~ for(int j = 0;j<n;j++){
			//~ cout << dp[j] << " ";
		//~ }
		//~ cout << "\n";
		
		
		res = min(res, max(dp[a], dp[b]));
	}
	
	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...