// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 3e5 +23, inf = LLONG_MAX, LG = 20;
int par[sze];
vector<int> graph[sze];
void dfs(int node,int p=-1){
par[node]=p;
for(auto v:graph[node]){
if(v!=p){
dfs(v,node);
}
}
}
pair<int,int> edge;
int dfs2(int node,int p=-1){
int sum=0;
vector<int> lst;
// cout<<node<<" "<<p<<" "<<edge.first<<" "<<edge.second<<endl;
for(auto v:graph[node]){
// to = make_pair(min(node,v),max(node,v));
if(v!=p && edge!=make_pair(min(node,v),max(node,v))){
lst.pb(dfs2(v,node));
}
}
sort(all(lst),greater<int>());
for(int i=1;i<=lst.size();i++){
sum=max(sum,lst[i-1]+i);
}
return sum;
}
void fast(){
int n,va,vb;
cin>>n>>va>>vb;
vector<int> yol;
for(int i =1;i<n;i++){
int u,v;
cin>>u>>v;
graph[u].pb(v);
graph[v].pb(u);
}
dfs(va);
for(int node= vb;node!=va;node = par[node]){
yol.pb(node);
}
// for(auto v:yol)cout<<v<<" ";cout<<endl;
int l =0;
int r = yol.size()-1;
int b = 0;
while(l<=r){
int mid = (l+r)/2;
edge = make_pair( min(yol[mid],par[yol[mid]]), max(yol[mid],par[yol[mid]]));
int a= dfs2(va);
int b = dfs2(vb);
if(a-b > 0){
b= mid;
l = mid+1;
}
else{
r = mid-1;
}
}
// cout<<b<<" : "<<yol[b]<<" "<<par[yol[b]]<<endl;
int ans = inf;
for(int j=b-1;j<=b+1;j++){
if(j>=0 && j<yol.size()){
edge = make_pair( min(yol[j],par[yol[j]]), max(yol[j],par[yol[j]]));
ans= min(ans,max(dfs2(va),dfs2(vb)));
}
}
assert(ans<inf);
putr(ans);
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int tt = 1;
// cin>>tt;
while(tt--){
fast();
}
return 0;
}
Compilation message
torrent.cpp: In function 'long long int dfs2(long long int, long long int)':
torrent.cpp:35:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=1;i<=lst.size();i++){
| ~^~~~~~~~~~~~
torrent.cpp: In function 'void fast()':
torrent.cpp:76:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if(j>=0 && j<yol.size()){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
304 ms |
22948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
