# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1267806 | newbie_t | Torrent (COI16_torrent) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vpi vector<pair<int, int>>
#define vpl vector<pair<ll, ll>>
#define a first
#define b second
#define pb push_back
#define vm vector<mi>
#define vmm vector<vector<mi>>
using namespace std;
const int MOD = 998244353;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,a,b; cin >> n >> a >> b;
a--,b--;
vii g(n);
for(int i = 1; i<n; i++){
int x,y; cin >> x >> y;
g[--x].pb(--y);
g[y].pb(x);
}
vi depth(n);
function<void(int,int)> dfs1;
dfs1 = [&](int s, int p){
if(p != -1) depth[s] = depth[p]+1;
for(int i: g[s]) if(i != p)
dfs1(i,s);
};
dfs1(a,-1);
vi path{b};
while(path[path.size()-1] != a)
for(int i: g[path[path.size()-1]])
if(depth[i]+1 == depth[path[path.size()-1]]){
path.pb(i);
break;
}
function<int(int,int,int)> dfs2;
dfs2 = [&](int s, int p, int stop){
vi next;
for(int i: g[s]) if(i != p && i != stop)
next.pb(dfs2(i,s,stop));
sort(next.rbegin(),next.rend());
int ans = 0;
for(int i = 0; i<next.size(); i++) uMax(ans,next[i]+i);
return ans+1;
};
int lo = 0, hi = path.size()-2;
while(lo<hi-1){
int m = (lo+hi)>>1;
int a1 = dfs2(b,-1,path[m+1]);
int a2 = dfs2(a,-1,path[m]);
if(a1<a2) lo = m;
else hi = m;
}
cout << min(max(dfs2(b,-1,path[lo+1]),dfs2(a,-1,path[lo])),max(dfs2(b,-1,path[hi+1]),dfs2(a,-1,path[hi])))-1 << "\n";
}