#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 lim2){
//cout<<"here "<<v<<' '<<trc<<' '<<lim2<<'\n';
int dem=pr[v].size()-1;
if(lim2<dem){dp[v]=n;return;}
for(int u:pr[v])if(u!=trc)
go(u,v,lim2-dem);
int cnt=0;
for(int u:pr[v])if(u!=trc){
if(dp[u]>=dem) cnt++;
else B[dp[u]]++;
}
//if(dem<=lim2)
dp[v]=dem;
for(int i=dem-1;i>0;i--){
//if(cnt<=lim2)
minn(dp[v],i-1+cnt);
//cout<<"haha "<<i<<' '<<cnt<<' '<<i-1+cnt<<'\n';
cnt+=B[i];B[i]=0;
}
//if(cnt<=lim2)
minn(dp[v],cnt);
//cout<<"now "<<v<<' '<<dp[v]<<' '<<lim2<<'\n';
}
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++;
//cout<<v<<' '<<val<<'\n';
for(int u:pr[v])if(u!=trc && u!=z){
dem++;
go(u,v,lim-val);
}
if(dem==0){
if(!GO(z,v,hav,lim))return 0;
dp[v]=dp[z];return 1;
}
for(int u:pr[v])if(u!=trc && u!=z){
if(dp[u]>hav+1) cnt++;
else B[dp[u]]++;
cout<<u<<' '<<dp[u]<<'\n';
}
///(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<<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 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:117:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
117 | int mid=b+e>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
326 ms |
91908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
