#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e7;
ll n,a,b,x,y,check[300005],trace[300005],c,dist[300005],canh,moc,pos=-1,hao;
vector<ll> ed[300005],pa,dp[300005];
void dfs(int u)
{
check[u]=1;
for (auto it: ed[u])
{
if (check[it]==0)
{
dfs(it);
trace[it]=u;
}
}
}
void dpontree(int u,int v)
{
if (u==v) return;
check[u]=1;
for (auto it: ed[u])
{
if (check[it]==0)
{
dpontree(it,v);
dp[u].push_back(dist[it]);
}
}
sort(dp[u].begin(),dp[u].end());
canh=0;
moc=1;
for (int i=dp[u].size()-1;i>=0;--i)
{
canh=max(canh,dp[u][i]+moc);
moc++;
}
dist[u]=canh;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n>>a>>b;
c=b;
for (int i=1;i<n;++i)
{
cin>>x>>y;
ed[x].push_back(y);
ed[y].push_back(x);
}
dfs(a);
while (b!=0)
{
pa.push_back(b);
b=trace[b];
}
b=c;
int l=0,r=pa.size()-2;
while (l<=r)
{
int mid=(l+r)/2;
for (int i=1;i<=n;++i) dp[i].clear();
memset(check,0,sizeof(check));
dpontree(b,pa[mid+1]);
dpontree(a,pa[mid]);
if (dist[b]<=dist[a])
{
pos=mid;
l=mid+1;
}
else r=mid-1;
}
if (pos==-1)
{
for (int i=1;i<=n;++i) dp[i].clear();
memset(check,0,sizeof(check));
dpontree(b,pa[1]);
cout<<dist[b];
return 0;
}
else
{
for (int i=1;i<=n;++i) dp[i].clear();
memset(check,0,sizeof(check));
dpontree(b,pa[pos+1]);
dpontree(a,pa[pos]);
hao=dist[a];
if (pos+2<pa.size())
{
for (int i=1;i<=n;++i) dp[i].clear();
memset(check,0,sizeof(check));
dpontree(b,pa[pos+2]);
dpontree(a,pa[pos+1]);
hao=min(hao,dist[b]);
}
cout<<hao;
return 0;
}
}
Compilation message
torrent.cpp: In function 'int main()':
torrent.cpp:90:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if (pos+2<pa.size())
| ~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
19544 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
372 ms |
39132 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |