#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 dp1[a]+dp2[b];
}
int main()
{
//freopen("","r",stdin);
//freopen("","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);
}
pre_dfs(a,0);
vec.push_back(0);
pre_dfs1(a,0);
ll ans=inf;
for(auto i:vec)
{
if(i!=0&&i!=a)
{
ans=min(ans,solve(i));
//cout<<i<<" "<<solve(i)<<'\n';
}
}
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 |
Incorrect |
13 ms |
21596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2041 ms |
53328 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
