#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
//#define int long long
void maxx(int &a,int b){if(b>a) a=b;}
void minn(int &a,int b){if(b<a) a=b;}
using ll = long long;
using ii = pair < int , int >;
const int MAX=1e6+3,inf=1e9,mod=1e9+7;
vector < int > pr[MAX];
//int tim=0,sz[MAX];
int pa[MAX];
int n;
int H[MAX];
void dfs(int v,int trc){
for(int u:pr[v])if(u!=trc){
pa[u]=v;
H[u]=H[v]+pr[u].size()-2;
dfs(u,v);
}
}
int dp[MAX];
int B[MAX];
void go(int v,int trc){
int S1=0,S2=-1;
for(int u:pr[v])if(u!=trc){
go(u,v);
dp[v]++;
if(S1<dp[u]){
S2=S1;S1=dp[u];
}else{
maxx(S2,dp[u]);
}
}
if(dp[v]>1) {
dp[v]+=S2;
}
}
int t;
//int lim;
bool GO(int v,int trc,int hav,int lim){
dp[v]=0;
if(v==t) return 1;
int z=pa[v];
int dem=0,cnt=0;
int val=H[v];
hav++;
for(int u:pr[v])if(u!=trc && u!=z){
if(dp[u]+val>lim) cnt++;
else B[dp[u]+val]++;
dem++;
}
if(dem==0){
if(!GO(z,v,hav,lim))return 0;
dp[v]=dp[z];return 1;
}
///(hav-need+1<dp[u])<=need;
//cout<<cnt<<' '<<need<<'\n';
int need=0;
while(need <dem && cnt>need){
if(hav-need+1>=0) cnt+=B[hav-need+1];
need++;
}
for(int u:pr[v])B[dp[u]]=0;
//cout<<lim<<' '<<need<<'\n';
cnt=need;
//cout<<"st "<<v<<' '<<hav<<' '<<cnt<<' '<<lim<<'\n';
lim-=cnt;
if(hav<cnt)return 0;
if(!GO(z,v,hav-cnt,lim))return 0;
dp[v]=dp[z]+cnt;
return 1;
}
int m;
bool ok(int val){
int lim=val;
if(!GO(m,0,0,lim))return 0;
//cout<<val<<' '<<m<<' '<<dp[m]<<'\n';
return dp[m]<=lim;
}
signed main(){
freopen("mousetrap.inp","r",stdin);
freopen("mousetrap.out","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n>>t>>m ;
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
pr[x].pb(y);
pr[y].pb(x);
}
dfs(t,0);
int x=m,pre=0;
while(x!=t){
for(int u:pr[x])if(u!=pre && u!=pa[x])
go(u,x);
pre=x;
x=pa[x];
}
int b=0,e=n-1,ans=n;
H[m]++;
//cout<<ok(5);return 0;
while(b<=e){
int mid=b+e>>1;
if(ok(mid)){
ans=mid;e=mid-1;
}else b=mid+1;
}
cout<<ans;
}
Compilation message
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:111:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | int mid=b+e>>1;
| ~^~
mousetrap.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen("mousetrap.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | freopen("mousetrap.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
