#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ll long long #define ull unsigned long long using namespace std; const int N=3e5+10; int n,s,a,b; vector<int> E[N],ok[N]; int fa[N][22],dep[N],hi[N],bfn[N],ibfn[N],bc=0; int L[N],R[N]; void pdfs(int u,int pa){ dep[u]=dep[pa]+1;fa[u][0]=pa; for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1];L[u]=bc+1; for(auto v:E[u]){ if(v==pa) continue; bfn[v]=++bc;ibfn[bc]=v; }R[u]=bc;hi[u]=1; for(auto v:E[u]){ if(v==pa) continue; pdfs(v,u);hi[u]=max(hi[u],hi[v]+1); } } int jump(int x,int k){ for(int i=19;i>=0;i--){ if((k>>i)&1) x=fa[x][i]; }return x; } int tv[N];set<int> st; int f[N],g[N],h[N],mnf[N],mnx[N]; struct pairing_heap{ struct node{ int ky,son,bro,id; }T[N];int tot=0; int Merge(int x,int y){ if(!x||!y) return x+y; if(T[x].ky>T[y].ky) swap(x,y); T[y].bro=T[x].son; T[x].son=y;return x; } int Merges(int x){ if(!x) return x; int y=T[x].bro,z=T[y].bro; if(!y) return x; T[x].bro=0,T[y].bro=0; return Merge(Merges(z),Merge(x,y)); } pii top(int x){ return mk(T[x].ky,T[x].id); } int pop(int x){ int y=Merges(T[x].son); T[x].son=0,T[x].bro=0; return y; } int add_node(int x,int id){ T[++tot]=(node){x,0,0,id}; return tot; } void clear_all(){ for(int i=1;i<=tot;i++) T[i]=(node){0,0,0,0};tot=0; } }DS;int Root[N]; //priority_queue<pii,vector<pii>,greater<pii>> pq[N]; void asi(int l,int r){ auto it=st.lower_bound(l); while(it!=st.end()){ if((*it)>r) break; g[*it]=1;st.erase(it); it=st.lower_bound(l); } } void tr(int x,int v){ if(!v) return ; int tx=jump(x,a-1); if(!fa[tx][0]) return ; f[bfn[fa[tx][0]]]=1; int l=L[fa[tx][0]],r=R[fa[tx][0]]; asi(l,bfn[tx]-1);asi(bfn[tx]+1,r); } void dfs(int u,int pa){ for(auto v:E[u]){ if(v==pa) continue; dfs(v,u); } int fmn=1e9,semn=1e9,hmx=0,semx=0; //last step if(!tv[u]) fmn=dep[u];hmx=1; for(auto v:E[u]){ if(v==pa) continue; if(mnx[v]<fmn) semn=fmn,fmn=mnx[v]; else if(mnx[v]<semn) semn=mnx[v]; if(hi[v]+1>hmx) semx=hmx,hmx=hi[v]+1; else if(hi[v]+1>semx) semx=hi[v]+1; }mnx[u]=fmn; if(hi[u]<=a) f[bfn[u]]=(mnx[u]<=dep[u]+b)?0:1; for(auto v:E[u]){ if(v==pa) continue; int nht=(hi[v]+1==hmx)?(semx):(hmx),tmn=(mnx[v]==fmn)?(semn):fmn; if(nht<=a) g[bfn[v]]=(tmn<=dep[u]+b)?0:1; } //other fmn=1e9,semn=1e9; if(!f[bfn[u]]) mnf[u]=dep[u]; for(auto v:E[u]){ if(v==pa) continue; if(mnf[v]<fmn) semn=fmn,fmn=mnf[v]; else if(mnf[v]<semn) semn=mnf[v]; mnf[u]=min(mnf[u],mnf[v]); } for(auto v:E[u]){ if(v==pa) continue; if(!g[bfn[v]]){ while(Root[v]){ pii p=DS.top(Root[v]); //cout<<v<<' '<<p.fi<<' '<<p.se<<endl; if(p.fi-dep[u]<=b){ h[p.se]=0;Root[v]=DS.pop(Root[v]); }else{ break; } } } int tmn=(mnf[v]==fmn)?(semn):(fmn); while(Root[v]){ pii p=DS.top(Root[v]); if(p.fi+tmn-2*dep[u]<=b){ h[p.se]=0;Root[v]=DS.pop(Root[v]); }else{ break; } } } for(auto v:E[u]){ if(v==pa) continue; Root[u]=DS.Merge(Root[u],Root[v]); } if(mnf[u]<=dep[u]+b){ h[u]=0; }else{ Root[u]=DS.Merge(Root[u],DS.add_node(dep[u],u)); } for(auto v:ok[u]){ tr(v,h[v]); } } bool DP(int v){ for(int i=1;i<=v;i++) tv[i]=0; for(int i=v+1;i<=n;i++) tv[i]=1; for(int i=0;i<=n;i++) f[i]=0,g[i]=0,h[i]=1,mnf[i]=1e9,mnx[i]=1e9; for(int i=0;i<=n;i++) st.insert(i); for(int i=1;i<=n;i++) Root[i]=0;DS.clear_all(); dfs(s,0); //for(int i=1;i<=n;i++) cout<<f[bfn[i]]<<' ';cout<<endl; //for(int i=1;i<=n;i++) cout<<g[bfn[i]]<<' ';cout<<endl; //for(int i=1;i<=n;i++) cout<<h[i]<<' ';cout<<endl; return f[bfn[s]]; } void slv(){ cin>>n>>s>>a>>b; for(int i=1;i<n;i++){ int u,v;cin>>u>>v; E[u].push_back(v); E[v].push_back(u); } if(a<=b){ cout<<1<<'\n'; }else{ pdfs(s,0); for(int i=1;i<=n;i++) ok[jump(i,b)].push_back(i); //cout<<DP(3)<<'\n'; int l=1,r=n; while(l<r){ int mid=(l+r)/2; //cout<<mid<<endl; if(DP(mid)) l=mid+1; else r=mid; }cout<<l<<'\n'; } } int main(){ //freopen("chess.in","r",stdin); //freopen("chess.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1;//cin>>t; while(t--) slv(); return 0; }