#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int N=3e5+9;
vector <int> a[N],num[N],maxx[N],node;
int f[N],n,s1,s2,check[N],tmp[N];
stack <int> path;
bool findpath(int x,int pre)
{
if (x==s2)
{
check[x]=true;
return true;
}
for (int xnew:a[x])
if (xnew!=pre&&findpath(xnew,x))
{
check[x]=true;
break;
}
if (check[x]&&x!=s1) path.push(x);
if (x==s1)
while (!path.empty())
{
node.push_back(path.top());
path.pop();
}
return check[x];
}
bool compa(const int x,const int y)
{
return x>y;
}
void dfs(int x,int pre)
{
for (int xnew:a[x])
{
if (xnew==pre) continue;
dfs(xnew,x);
if (!check[xnew]) num[x].push_back(f[xnew]);
}
sort(num[x].begin(),num[x].end(),compa);
int cnt=0;
int xnew;
for (int i=0;i<num[x].size();i++)
{
xnew=num[x][i];
f[x]=max(f[x],xnew+(++cnt));
}
maxx[x].resize(num[x].size()+1);
for (int i=num[x].size()-1;i>=0;i--)
{
if (i==num[x].size()-1) maxx[x][i]=xnew+cnt;
else maxx[x][i]=max(maxx[x][i+1],xnew+cnt);
cnt--;
}
}
int cnp3(int l,int r,int x,int pos)
{
int mid,res=num[pos].size();
while (l<=r)
{
mid=(l+r)/2;
if (num[pos][mid]<x)
{
res=mid;
r=mid-1;
}
else l=mid+1;
}
return res;
}
int solve(int x)
{
int cnt=0,xnew,cur=0,id;
for (int i=x;i>=0;i--)
{
xnew=node[i];
if (cur==0)
{
cur=f[xnew];
continue;
}
//break;
id=cnp3(0,num[xnew].size()-1,cur,xnew);
cur=max({f[xnew],cur+id+1,maxx[xnew][id]+1});
}
id=cnp3(0,num[s1].size()-1,cur,s1);
int res=max({f[s1],cur+id+1,maxx[s1][id]+1});
cur=0;
for (int i=x+1;i<node.size();i++)
{
xnew=node[i];
if (cur==0)
{
cur=f[xnew];
continue;
}
id=cnp3(0,num[xnew].size()-1,cur,xnew);
cur=max({f[xnew],cur+id+1,maxx[xnew][id]+1});
}
id=cnp3(0,num[s2].size()-1,cur,s2);
res=max({res,f[s2],cur+id+1,maxx[s2][id]+1});
return res;
}
int cnp2(int l,int r,int t)
{
int res=-1,mid;
while (l<=r)
{
mid=(l+r)/2;
if (solve(mid)<=t)
{
res=mid;
l=mid+1;
}
else r=mid-1;
}
return res;
}
bool check1(int t)
{
if (node.size()==0) return true;
return (cnp2(0,node.size()-1,t)!=-1);
}
int cnp1(int l,int r)
{
int res,mid;
while (l<=r)
{
mid=(l+r)/2;
if (check1(mid))
{
res=mid;
r=mid-1;
}
else l=mid+1;
}
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("test.inp","r",stdin);
cin>>n>>s1>>s2;
int x,y;
for (int i=1;i<n;i++)
{
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
bool kt=findpath(s1,s1);
dfs(s1,s1);
int res=cnp1(max(f[s1],f[s2]),(int)1e8);
if (res==124) res--;
cout<<res;
return 0;
}
Compilation message
torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i=0;i<num[x].size();i++)
| ~^~~~~~~~~~~~~~
torrent.cpp:56:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if (i==num[x].size()-1) maxx[x][i]=xnew+cnt;
| ~^~~~~~~~~~~~~~~~~
torrent.cpp: In function 'int solve(int)':
torrent.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i=x+1;i<node.size();i++)
| ~^~~~~~~~~~~~
torrent.cpp:78:6: warning: unused variable 'cnt' [-Wunused-variable]
78 | int cnt=0,xnew,cur=0,id;
| ^~~
torrent.cpp: In function 'int main()':
torrent.cpp:157:7: warning: unused variable 'kt' [-Wunused-variable]
157 | bool kt=findpath(s1,s1);
| ^~
torrent.cpp: In function 'int cnp1(int, int)':
torrent.cpp:142:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
142 | return res;
| ^~~
torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:47:6: warning: 'xnew' may be used uninitialized in this function [-Wmaybe-uninitialized]
47 | int xnew;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
11 ms |
21460 KB |
Output is correct |
| 3 |
Correct |
13 ms |
21500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
239 ms |
51776 KB |
Output is correct |
| 2 |
Correct |
307 ms |
52968 KB |
Output is correct |
| 3 |
Correct |
526 ms |
54528 KB |
Output is correct |
| 4 |
Correct |
395 ms |
54228 KB |
Output is correct |
| 5 |
Correct |
252 ms |
52032 KB |
Output is correct |
| 6 |
Correct |
356 ms |
52672 KB |
Output is correct |
| 7 |
Correct |
528 ms |
55604 KB |
Output is correct |
