#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;
if(n<=1000)
{
for(auto i:vec)
{
if(i!=0&&i!=a)
{
ans=min(ans,solve(i));
//cout<<i<<" "<<solve(i)<<'\n';
}
}
}
else
{
ll l=1,r=vec.size()-1;
while(l<r)
{
ll mid=(l+r)/2;
ll tmp1=solve(vec[mid]),tmp2=solve(vec[mid+1]);
ans=min(ans,max(tmp1,tmp2));
if(tmp1>tmp2)
{
l=mid+1;
}
else r=mid-1;
}
}
cout<<ans;
}
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 |
Correct |
14 ms |
21596 KB |
Output is correct |
| 2 |
Correct |
12 ms |
21596 KB |
Output is correct |
| 3 |
Correct |
14 ms |
21596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
793 ms |
50204 KB |
Output is correct |
| 2 |
Correct |
741 ms |
58388 KB |
Output is correct |
| 3 |
Correct |
664 ms |
54828 KB |
Output is correct |
| 4 |
Correct |
699 ms |
54208 KB |
Output is correct |
| 5 |
Correct |
778 ms |
47860 KB |
Output is correct |
| 6 |
Correct |
656 ms |
50092 KB |
Output is correct |
| 7 |
Correct |
661 ms |
53580 KB |
Output is correct |
