This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define LL long long
#define Rep(i,x,y) for(int i = (x), stOxrj = (y); i <= stOxrj; ++i)
#define Irep(i,x,y) for(int i = (x), stOxrj = (y); i >= stOxrj; --i)
#define il inline
#define let const auto
#define ci const int&
#define VEC vector<int>
#define pb emplace_back
#define MP make_pair
#define PA pair<int, int>
#define fi first
#define se second
#define IT iterator
using namespace std;
il int read(){
int res = 0, flag = 1; char c = getchar();
while( c < '0' || c > '9' ){ if( c == '-' ) flag = -1; c = getchar(); }
while( c >= '0' && c <= '9' ) res = res * 10 + c - '0', c = getchar();
return res * flag;
}
const int N = 3e5 + 20;
VEC e[N];
int ba, bb, n, s, t;
bool same(ci u, ci v){
return u + v == ba + bb && abs(u - v) == abs(ba - bb);
}
int fa[N], f[N];
int nb[N];
void dfs(int u, int fat){
fa[u] = fat;
for(int v : e[u]) if(v != fat && !same(u, v)) dfs(v, u);
int res = 0, cnt = 0;
for(int v : e[u]) if(v != fat && !same(u, v)) nb[++cnt] = f[v];
sort(nb + 1, nb + cnt + 1, [&](ci A, ci B){ return A > B; });
Rep(i, 1, cnt) res = max(res, i + nb[i]);
f[u] = res;
}
int link[N], ln;
PA Solve(int x){
ba = link[x], bb = link[x + 1];
dfs(s, 0), dfs(t, 0);
return MP(f[s], f[t]);
}
signed main(){
// freopen("rorrent.in", "r", stdin);
// freopen("rorrent.out", "w", stdout);
n = read(), s = read(), t = read();
Rep(i, 2, n){
int u = read(), v = read();
e[u].pb(v), e[v].pb(u);
}
dfs(t, 0);
int ss = s;
link[++ln] = s;
while(ss != t) link[++ln] = ss = fa[ss];
PA cur;
int l = 1, r = ln - 1;
while(l < r){
int mid = l + r >> 1;
cur = Solve(mid);
if(cur.fi > cur.se) l = mid + 1;
else r = mid;
}
cur = Solve(l);
int ans = max(cur.fi, cur.se);
if(l != 1){
cur = Solve(l - 1);
ans = min(ans, max(cur.fi, cur.se));
}
cout<<ans<<'\n';
return 0;
}
Compilation message (stderr)
torrent.cpp: In function 'int main()':
torrent.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = l + r >> 1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |