#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second #define mk make_pair const int N=3e5+10,inf=1e9+10; vector<int> E[N]; int f[N],g[N],h[N]; int fa[N][22],siz[N],hi[N],dep[N],hs[N],dfn[N],rk[N],top[N]; int idx[N],bl[N],br[N]; int n,s,a,b; void dfs1(int u,int pr){ dep[u]=dep[pr]+1; fa[u][0]=pr;for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; pii hs0=mk(0,0); for(auto v:E[u]){ if(v==pr) continue; dfs1(v,u); hi[u]=max(hi[u],hi[v]); siz[u]+=siz[v]; hs0=max(hs0,mk(siz[v],v)); }hs[u]=hs0.se; hi[u]++;siz[u]++; }int dc=0,tot=0; void dfs2(int u,int pr,int tp){ dfn[u]=++dc;rk[dc]=u;top[u]=tp;bl[u]=tot+1; for(auto v:E[u]){ if(v==pr) continue; if(v!=hs[u]) idx[v]=++tot; }br[u]=tot; for(auto v:E[u]){ if(v==hs[u]) dfs2(v,u,tp); }for(auto v:E[u]){ if(v==pr) continue; if(v!=hs[u]) dfs2(v,u,v); } } #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 struct sgt1{ int T[N<<2],tg[N<<2]; void pu(int p){ T[p]=min(T[ls],T[rs]); }void pd(int p){ T[ls]=min(tg[p],T[ls]); T[rs]=min(tg[p],T[rs]); tg[ls]=min(tg[p],tg[ls]); tg[rs]=min(tg[p],tg[rs]); tg[p]=inf; }void bd(int p,int l,int r){ tg[p]=inf;T[p]=inf; if(l==r) return ; bd(ls,l,mid);bd(rs,mid+1,r); }void upd(int p,int l,int r,int pl,int pr,int v){ //cout<<p<<' '<<l<<' '<<r<<' '<<pl<<' '<<pr<<' '<<v<<endl; if(pl>pr) return ; if(pl<=l&&r<=pr){ T[p]=min(T[p],v);tg[p]=min(tg[p],v);return ; }pd(p); if(pl<=mid) upd(ls,l,mid,pl,pr,v); if(pr>mid) upd(rs,mid+1,r,pl,pr,v);pu(p); }int qry(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr) return T[p]; int res=inf;pd(p); if(pl<=mid) res=min(res,qry(ls,l,mid,pl,pr)); if(pr>mid) res=min(res,qry(rs,mid+1,r,pl,pr));return res; } }sgth,sgtuf,sgtug,sgtuhg; struct sgt2{ int T[N<<2],tg[N<<2]; void pu(int p){ T[p]=max(T[ls],T[rs]); }void pd(int p){ T[ls]=max(tg[p],T[ls]); T[rs]=max(tg[p],T[rs]); tg[ls]=max(tg[p],tg[ls]); tg[rs]=max(tg[p],tg[rs]); tg[p]=0; }void bd(int p,int l,int r){ tg[p]=0;T[p]=0; if(l==r) return ; bd(ls,l,mid);bd(rs,mid+1,r); }void upd(int p,int l,int r,int pl,int pr,int v){ if(pl>pr) return ; //cout<<pl<<' '<<pr<<' '<<v<<endl; if(pl<=l&&r<=pr){ T[p]=max(T[p],v);tg[p]=max(tg[p],v);return ; }pd(p); if(pl<=mid) upd(ls,l,mid,pl,pr,v); if(pr>mid) upd(rs,mid+1,r,pl,pr,v);pu(p);//cout<<p<<' '<<T[p]<<endl; }int qry(int p,int l,int r,int pl,int pr){ //cout<<T[p]<<' '<<l<<' '<<r<<' '<<pl<<' '<<pr<<endl; if(pl<=l&&r<=pr) return T[p]; int res=0;pd(p); if(pl<=mid) res=max(res,qry(ls,l,mid,pl,pr)); if(pr>mid) res=max(res,qry(rs,mid+1,r,pl,pr));return res; } }sgtf; struct sgt3{ int T[N<<2],tg[N<<2]; void pu(int p){ T[p]=min(T[ls],T[rs]); }void pd(int p){ T[ls]=max(tg[p],T[ls]); T[rs]=max(tg[p],T[rs]); tg[ls]=max(tg[p],tg[ls]); tg[rs]=max(tg[p],tg[rs]); tg[p]=0; }void bd(int p,int l,int r){ tg[p]=0;T[p]=0; if(l==r) return ; bd(ls,l,mid);bd(rs,mid+1,r); }void upd(int p,int l,int r,int pl,int pr,int v){ if(pl>pr) return ; //cout<<pl<<' '<<pr<<' '<<v<<endl; if(pl<=l&&r<=pr){ T[p]=max(T[p],v);tg[p]=max(tg[p],v);return ; }pd(p); if(pl<=mid) upd(ls,l,mid,pl,pr,v); if(pr>mid) upd(rs,mid+1,r,pl,pr,v);pu(p);//cout<<p<<' '<<T[p]<<endl; }int qry(int p,int l,int r,int pl,int pr){ //cout<<T[p]<<' '<<l<<' '<<r<<' '<<pl<<' '<<pr<<endl; if(pl<=l&&r<=pr) return T[p]; int res=inf;pd(p); if(pl<=mid) res=min(res,qry(ls,l,mid,pl,pr)); if(pr>mid) res=min(res,qry(rs,mid+1,r,pl,pr));return res; } }sgthg,sgtg; bool cmp1(int a,int b){ return dep[a]>dep[b]; }int tr[N];bool vis[N]; int main(){ 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;return 0; }dfs1(s,0);dfs2(s,0,s);hi[0]=inf;//1 //for(int i=1;i<=n;i++) cout<<bl[i]<<' '<<br[i]<<endl; //for(int i=1;i<=n;i++) cout<<hi[i]<<' '; //return 0; sgtuf.bd(1,1,n);sgtug.bd(1,1,n);sgtuhg.bd(1,1,n); //for(int j=1;j<=n;j++) cout<<sgtuf.qry(1,1,n,dfn[j],dfn[j])<<' ';cout<<endl; for(int i=1;i<=n;i++){ //cout<<"JP8AKIOI1 "<<hi[i]<<endl; int now=i; if(hi[i]>a) continue; int to=b; for(int j=19;j>=0;j--){ if(hi[fa[now][j]]>a) continue; if(to>=(1<<j)) now=fa[now][j],to-=(1<<j); } //cout<<"JP8AKIOI2 "<<hi[i]<<endl; int now2=i; sgtug.upd(1,1,n,bl[i],br[i],i); sgtuhg.upd(1,1,n,dfn[i],dfn[i],i); //cout<<now<<endl; //cout<<now2<<' '<<now<<' '<<i<<endl; while(dep[top[now2]]>dep[now]){ //cout<<"JP8AKIOI3 "<<now<<endl; //cout<<now2<<' '<<now<<' '<<i<<endl; sgtuf.upd(1,1,n,dfn[top[now2]],dfn[now2],i); sgtug.upd(1,1,n,bl[top[now2]],br[fa[now2][0]],i);; sgtuhg.upd(1,1,n,dfn[fa[top[now2]][0]],dfn[fa[top[now2]][0]],i); sgtug.upd(1,1,n,bl[fa[top[now2]][0]],idx[top[now2]]-1,i); sgtug.upd(1,1,n,idx[top[now2]]+1,br[fa[top[now2]][0]],i); //cout<<"JPcout<<p<<' '<<l<<' '<<r<<' '<<pl<<' '<<pr<<' '<<v<<endl;[now2]][0]; now2=fa[top[now2]][0]; }//cout<<now<<' '<<now2<<endl; sgtuf.upd(1,1,n,dfn[now],dfn[now2],i); sgtug.upd(1,1,n,bl[now],br[fa[now2][0]],i); //for(int j=1;j<=n;j++) cout<<sgtuf.qry(1,1,n,dfn[j],dfn[j])<<' ';cout<<endl; }//return 0; sgtf.bd(1,1,n);sgtg.bd(1,1,n);sgthg.bd(1,1,n);sgth.bd(1,1,n); //for(int j=1;j<=n;j++) cout<<sgthg.qry(1,1,n,dfn[j],dfn[j])<<' ';cout<<endl; for(int i=1;i<=n;i++) sgthg.upd(1,1,n,dfn[i],dfn[i],i); for(int i=1;i<=n;i++){ int vl=sgtuf.qry(1,1,n,dfn[i],dfn[i]); //cout<<vl<<' '; if(vl<inf){ vis[i]=1; sgtf.upd(1,1,n,dfn[i],dfn[i],vl); int to=b,now1=i; for(int j=19;j>=0;j--){ if(!fa[now1][j]) continue; if(to>=(1<<j)) now1=fa[now1][j],to-=(1<<j); }int now2=i; while(dep[top[now2]]>dep[now1]){ sgth.upd(1,1,n,dfn[top[now2]],dfn[now2],vl); now2=fa[top[now2]][0]; }sgth.upd(1,1,n,dfn[now1],dfn[now2],vl); } vl=sgtuhg.qry(1,1,n,i,i);//cout<<endl<<vl<<' '<<(vl<inf)<<endl; if(vl<inf) sgthg.upd(1,1,n,i,i,vl); //cout<<vl<<endl; //for(int j=1;j<=n;j++) cout<<sgthg.qry(1,1,n,dfn[j],dfn[j])<<' ';cout<<endl; vl=sgtug.qry(1,1,n,i,i); if(vl<inf) sgtg.upd(1,1,n,i,i,vl); }for(int i=1;i<=n;i++) tr[i]=i; //for(int j=1;j<=n;j++) cout<<sgtf.qry(1,1,n,dfn[j],dfn[j])<<' ';cout<<endl; //for(int j=1;j<=n;j++) cout<<sgtg.qry(1,1,n,j,j)<<' ';cout<<endl; sort(tr+1,tr+n+1,cmp1); int it=1; for(int i=1;i<=n;i++){ //for(int j=1;j<=n;j++) cout<<sgth.qry(1,1,n,dfn[j],dfn[j])<<' ';cout<<endl; //cout<<"jp8akioi 1:"<<it<<endl; while(it<=n&&(dep[tr[i]]-a<dep[tr[it]])){ //cout<<it<<' '; if(!vis[tr[it]]){ //cout<<"!"<<' '; int vl=sgtf.qry(1,1,n,dfn[tr[it]],dfn[tr[it]]); vis[tr[it]]=1; int to=b,now1=tr[it]; for(int j=19;j>=0;j--){ if(!fa[now1][j]) continue; if(to>=(1<<j)) now1=fa[now1][j],to-=(1<<j); }int now2=tr[it]; //cout<<now2<<' '<<now1<<endl; while(dep[top[now2]]>dep[now1]){ sgth.upd(1,1,n,dfn[top[now2]],dfn[now2],vl); now2=fa[top[now2]][0]; }sgth.upd(1,1,n,dfn[now1],dfn[now2],vl); }it++; }//cout<<endl; int to=b,now1=tr[i]; for(int j=19;j>=0;j--){ if(!fa[now1][j]) continue; if(to>=(1<<j)) now1=fa[now1][j],to-=(1<<j); }int now2=tr[i];//cout<<tr[i]<<' '<<now2<<' '<<now1<<endl; //cout<<1<<endl; //cout<<now2<<' '<<now1<<endl; while(dep[top[now2]]>dep[now1]){ int vl=sgthg.qry(1,1,n,dfn[top[now2]],dfn[fa[now2][0]]); vl=min(vl,sgtg.qry(1,1,n,idx[top[now2]],idx[top[now2]])); //cout<<idx[now2]<<endl; sgth.upd(1,1,n,dfn[tr[i]],dfn[tr[i]],vl); now2=fa[top[now2]][0]; } //cout<<now1<<' '<<now2<<endl; int vg; if(now1!=now2) vg=sgthg.qry(1,1,n,dfn[now1],dfn[fa[now2][0]]); //cout<<vg<<' '<<dfn[now1]<<' '<<dfn[fa[now2][0]];cout<<endl; if(now1!=now2) sgth.upd(1,1,n,dfn[tr[i]],dfn[tr[i]],vg); to=a-1;now1=tr[i]; for(int j=19;j>=0;j--){ if((to>>j)&1) now1=fa[now1][j]; }if(!fa[now1][0]) continue; //cout<<"jp8akioi 2:"<<endl; int pr1=fa[now1][0]; int vh=sgth.qry(1,1,n,dfn[tr[i]],dfn[tr[i]]); //cout<<vh<<' '<<pr1<<endl; sgtf.upd(1,1,n,dfn[pr1],dfn[pr1],vh); if(!idx[now1]){ sgtg.upd(1,1,n,bl[pr1],br[pr1],vh); }else{ sgthg.upd(1,1,n,dfn[pr1],dfn[pr1],vh); sgtg.upd(1,1,n,bl[pr1],idx[now1]-1,vh); sgtg.upd(1,1,n,idx[now1]+1,br[pr1],vh); } }cout<<sgtf.qry(1,1,n,dfn[s],dfn[s]); return 0; } /* .........#######################................###########################........... ........#.......................#..............#...........................#.......... .......#.............#...........#............#...............#######.......#......... ......#..............#............#..........#..........######...............#........ .....#...............#.............#........#...........#.....................#....... ....#................#..............#......#............#......#...............#...... ...#.........#################.......#....#.............#......#................#..... ..#..................#.......#........#..#..............##############...........#.... .#..................#........#.........##.....................#..................#... .#.................#.........#.........##.....................#..................#... .#.................#........#..........##...............#.....#...#..............#... ..#...............#........#..........#..#..............#......#....#............#.... ...#.............#.........#.........#....#............#.......#.....#..........#..... ....#...........#.....#...#.........#......#................#..#...............#...... .....#.........#.......###.........#........#................###..............#....... ......#...........................#..........#...............................#........ .......###########################............###############################......... */