#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define compact(x) (x).erase(all(x),(x).end())
#define pb(x) push_back(x)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
const int inf = 1e9;
const ll linf = 1e18;
const double pi = acos(-1);
const int N = 3e5 + 5;
const int LOG = 32 - __builtin_clz(N);
vector<int> a[N];
int n;
int r1, r2;
int pa[N][LOG];
int h[N];
void dfs(int u,int p = -1){
for (int i = 1; (1 << i) <= h[u]; i++){
pa[u][i] = pa[pa[u][i-1]][i-1];
}
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i];
if (v == p) continue;
pa[v][0] = u;
h[v] = h[u] + 1;
dfs(v,u);
}
}
int cal(int u,int p,int f){
vector<int> tmp;
for (int v : a[u]){
if (v == p || v == f) continue;
tmp.push_back(cal(v,u,f));
}
int res = 0;
sort(all(tmp),greater<int>());
int k = 0;
for (int i = 0; i < tmp.size(); i++){
k = max(tmp[i] + i + 1,k);
}
res += k;
return res;
}
int getAns(int x){
return max(cal(r1,-1,x), cal(r2,-1,pa[x][0]));
}
int solve(){
if (pa[r2][0] == r1) return max(cal(r1,-1,r2),cal(r2,-1,r1));
int res = r2;
int k = 31 - __builtin_clz(h[r2] - 1);
int step = 0;
for (int i = k; i >= 0; i--){
if (step + (1 << i) > h[r2] - 1) continue;
int tmp = pa[res][i];
// cout << tmp << " " << check(tmp) << "\n";
int f = cal(r1,-1,tmp);
int g = cal(r2,-1,pa[tmp][0]);
if (f >= g){
res = tmp;
step += (1 << i);
}
}
// cout << res << "\n";
// return getAns(res);
return min(getAns(res),getAns(pa[res][0]));
}
int solve2(){
int cur = r2;
int res = inf;
while(cur != r1){
int tmp = getAns(cur);
cout << tmp << "\n";
res = min(res,tmp);
cur = pa[cur][0];
}
return res;
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
#define TEXT "torrent"
if (fopen(TEXT".inp","r")){
freopen(TEXT".inp","r",stdin);
freopen(TEXT".out","w",stdout);
}
cin >> n >> r1 >> r2;
for (int i = 1; i < n; i++){
int u,v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(r1);
cout << solve() << "\n";
// cout << solve2() << "\n";
return 0;
}
Compilation message (stderr)
torrent.cpp: In function 'int main()':
torrent.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen(TEXT".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | freopen(TEXT".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |