#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int llo;
#define mp make_pair
#define pb push_back
vector<llo> st;
vector<llo> path;
llo a,b,c,d;
vector<llo> adj[300010];
llo vis[300010];
void dfs(llo no){
if(no==b-1){
for(llo i=0;i<st.size();i++){
path.pb(st[i]);
}
}
for(llo j=0;j<adj[no].size();j++){
llo nn=adj[no][j];
if(vis[nn]==1){
continue;
}
st.pb(nn);
vis[nn]=1;
dfs(nn);
st.pop_back();
}
}
llo dfs2(llo no){
// cout<<no<<" ";
vector<llo> pp;
for(llo j=0;j<adj[no].size();j++){
llo nn=adj[no][j];
if(vis[nn]==0){
if((no==c and nn==d) or (no==d and nn==c)){
continue;
}
vis[nn]=1;
pp.pb(dfs2(nn));
}
}
if(pp.size()==0){
return 0;
}
sort(pp.begin(),pp.end());
llo ma=0;
/*if(no==a-1){
for(llo i=0;i<pp.size();i++){
cout<<pp[i]<<" ";
}
cout<<endl;
}*/
for(llo i=0;i<pp.size();i++){
ma=max(ma,(i+1)+pp[pp.size()-1-i]);
}
return ma;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
llo n;
cin>>n>>a>>b;
llo x,y;
for(llo i=0;i<n-1;i++){
cin>>x>>y;
adj[x-1].pb(y-1);
adj[y-1].pb(x-1);
}
st.pb(a-1);
memset(vis,0,sizeof(vis));
dfs(a-1);
llo low=0;
llo high=path.size()-2;
/*for(llo i=0;i<path.size();i++){
cout<<path[i]<<" ";
}
cout<<endl;*/
while(low<high-1){
llo mid=(low+high)/2;
memset(vis,0,sizeof(vis));
c=path[mid];
d=path[mid+1];
vis[a-1]=1;
vis[b-1]=1;
llo aa=dfs2(a-1);
llo bb=dfs2(b-1);
if(aa<bb){
low=mid;
}
else{
high=mid;
}
}
llo ma=4000000;
for(llo j=low;j<high+1;j++){
memset(vis,0,sizeof(vis));
c=path[j];
d=path[j+1];
vis[a-1]=1;
llo aa=dfs2(a-1);
// cout<<endl;
vis[b-1]=1;
llo bb=dfs2(b-1);
// cout<<endl;
// cout<<aa<<":"<<bb<<endl;
ma=min(ma,max(aa,bb));
// cout<<max(aa,bb)<<endl;
}
cout<<ma<<endl;
return 0;
}
Compilation message
torrent.cpp: In function 'void dfs(llo)':
torrent.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo i=0;i<st.size();i++){
~^~~~~~~~~~
torrent.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo j=0;j<adj[no].size();j++){
~^~~~~~~~~~~~~~~
torrent.cpp: In function 'llo dfs2(llo)':
torrent.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo j=0;j<adj[no].size();j++){
~^~~~~~~~~~~~~~~
torrent.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo i=0;i<pp.size();i++){
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
13 ms |
9720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
613 ms |
27140 KB |
Output is correct |
| 2 |
Correct |
678 ms |
28100 KB |
Output is correct |
| 3 |
Correct |
839 ms |
29276 KB |
Output is correct |
| 4 |
Correct |
643 ms |
28656 KB |
Output is correct |
| 5 |
Correct |
730 ms |
26360 KB |
Output is correct |
| 6 |
Correct |
551 ms |
27076 KB |
Output is correct |
| 7 |
Correct |
547 ms |
29940 KB |
Output is correct |
