#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=3e5+5;
const ll inf=2e18;
int n,a,b,dp1[maxN+1],dp2[maxN+1],h[maxN+1];
vector<int> adj[maxN+1],adj_a[maxN+1],adj_b[maxN+1],vec;
bool ck[maxN+1];
void pre_dfs(int u,int p)
{
if(u==b)
{
ck[u]=true;
return;
}
for(auto v:adj[u])
{
if(v!=p)
{
h[v]=h[u]+1;
pre_dfs(v,u);
if(ck[v])
{
ck[u]=true;
}
}
}
}
void pre_dfs1(int u,int p)
{
vec.push_back(u);
for(auto v:adj[u])
{
if(v!=p&&ck[v])
{
pre_dfs1(v,u);
}
}
}
void build(int u,int p,int pos,bool ok)
{
for(auto v:adj[u])
{
if(v!=p)
{
if(ok&&h[v]>h[pos])
{
adj_b[u].push_back(v);
adj_b[v].push_back(u);
}
else
{
if(v!=pos)
{
adj_a[u].push_back(v);
adj_a[v].push_back(u);
}
}
build(v,u,pos,(ok||(v==pos)));
}
}
}
void clr()
{
for(int i=1;i<=n;i++)
{
adj_a[i].clear();
adj_b[i].clear();
dp1[i]=0;
dp2[i]=0;
}
}
void dfs1(int u,int p)
{
vector<int> ve;
for(auto v:adj_a[u])
{
if(v!=p)
{
dfs1(v,u);
ve.push_back(v);
}
}
sort(ve.begin(),ve.end(),[&](int x,int y)
{
return dp1[x]>dp1[y];
});
dp1[u]=0;
for(int i=1;i<=ve.size();i++)
{
int v=ve[i-1];
dp1[u]=max(dp1[u],dp1[v]+i);
}
}
void dfs2(int u,int p)
{
vector<int> ve;
for(auto v:adj_b[u])
{
if(v!=p)
{
dfs2(v,u);
ve.push_back(v);
}
}
sort(ve.begin(),ve.end(),[&](int x,int y)
{
return dp2[x]>dp2[y];
});
dp2[u]=0;
for(int i=1;i<=ve.size();i++)
{
int v=ve[i-1];
dp2[u]=max(dp2[u],dp2[v]+i);
}
}
ll solve(int pos)
{
clr();
build(a,0,pos,0);
dfs1(a,0);
dfs2(b,0);
return max(dp1[a],dp2[b]);
}
bool check(int pos)
{
clr();
build(a,0,pos,0);
dfs1(a,0);
dfs2(b,0);
return (dp1[a]>dp2[b]);
}
int main()
{
//freopen("torrent.inp","r",stdin);
//freopen("torrent.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>a>>b;
if(a>b)
{
swap(a,b);
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
h[1]=1;
pre_dfs(a,0);
pre_dfs1(a,0);
ll ans=inf;
ll l=1,r=vec.size()-1;
while(l<r)
{
ll mid=(l+r)/2;
ans=min(ans,max(solve(vec[mid]),solve(vec[mid+1])));
if(solve(vec[mid])>solve(vec[mid+1]))
{
l=mid+1;
}
else r=mid-1;
}
cout<<min(ans,solve(vec[l]));
}
Compilation message
torrent.cpp: In function 'void dfs1(int, int)':
torrent.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=1;i<=ve.size();i++)
| ~^~~~~~~~~~~
torrent.cpp: In function 'void dfs2(int, int)':
torrent.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=1;i<=ve.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
21600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1290 ms |
54256 KB |
Output is correct |
| 2 |
Correct |
1424 ms |
62456 KB |
Output is correct |
| 3 |
Correct |
1339 ms |
59020 KB |
Output is correct |
| 4 |
Correct |
1395 ms |
58336 KB |
Output is correct |
| 5 |
Correct |
1225 ms |
51796 KB |
Output is correct |
| 6 |
Correct |
1071 ms |
54176 KB |
Output is correct |
| 7 |
Correct |
1095 ms |
57728 KB |
Output is correct |
