#include <bits/stdc++.h> using namespace std; #define int long long int n,r,a,b; int dep[500300],siz[500300],cs[500300]; int dfn[500300],loc[500300],tk; int lst[500300]; int mxd[500300]; int fa[500300],fab[500300],faa[500300],faa_[500300]; bool f[500300],g[500300],h[500300]; int mn[500300],mx[500300]; vector<int>gr[500300],remg1[500300],P[500300]; struct node{ int f,g; node(int F=1e18,int G=0){ f=F; g=G; } friend node operator +(const node A,const node B){ return node(min(A.f,B.f),A.g+B.g); } }w[500300<<2]; #define lc(x) (x<<1) #define rc(x) (x<<1|1) inline void upd(int x){ w[x]=w[lc(x)]+w[rc(x)]; } inline void mod(int x,int l,int r,int c,node A){ if(l==r){ w[x]=A; return ; } int mid=l+r>>1; if(c<=mid)mod(lc(x),l,mid,c,A); else mod(rc(x),mid+1,r,c,A); upd(x); } inline node gt(int x,int l,int r,int L,int R){ if(L>R)return node(2*n,0); if(L<=l&&r<=R)return w[x]; int mid=l+r>>1; node res; if(L<=mid)res=res+gt(lc(x),l,mid,L,R); if(R>mid)res=res+gt(rc(x),mid+1,r,L,R); return res; } inline void dfs(int u){ dep[u]=dep[fa[u]]+1; lst[dep[u]]=u; mn[u]=mx[u]=u; P[dep[u]].push_back(u); mxd[u]=0; if(dep[u]>b)fab[u]=lst[dep[u]-b]; else fab[u]=0; if(dep[u]>a)faa[u]=lst[dep[u]-a]; else faa[u]=0; if(dep[u]>a-1)faa_[u]=lst[dep[u]-(a-1)]; else faa_[u]=0; loc[dfn[u]=++tk]=u; siz[u]=1; for(int v:gr[u])if(v!=fa[u]){ fa[v]=u; dfs(v); siz[u]+=siz[v]; mn[u]=min(mn[u],mn[v]); mx[u]=max(mx[u],mx[v]); mxd[u]=max(mxd[u],mxd[v]+1); } } inline void bd(int x,int l,int r){ if(l==r){ w[x]=node(f[loc[x]]?dep[loc[x]]:2*n,g[loc[x]]); return ; } int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); upd(x); } inline void up(int x){ mod(1,1,n,dfn[x],node(f[loc[x]]?dep[loc[x]]:2*n,g[loc[x]])); } inline void modf(int x,bool p){ if(f[x]==p)return ; f[x]=p; up(x); } inline void modg(int x,bool p){ if(g[x]==p)return ; g[x]=p; up(x); } inline void uph(int x){ if(faa[x]==0)return ; if(h[x])return ; modf(faa[x],0); vector<int>T=remg1[faa[x]]; remg1[faa[x]].clear(); for(int y:T) if(y==faa_[x])remg1[faa[x]].push_back(y); else modg(y,0); } inline node gt(int u){ return gt(1,1,n,dfn[u],dfn[u]+siz[u]-1); } inline void init(int lim){ memset(f,1,sizeof(f)); memset(g,1,sizeof(g)); memset(h,0,sizeof(h)); for(int d=n;d>=1;d--) for(int u:P[d]) if(mxd[u]<a){ f[u]=mn[u]<=lim; int S=0,nd=0; for(int v:gr[u])if(v!=fa[u])nd++,S+=f[v]; nd--; for(int v:gr[u])if(v!=fa[u]){ S-=f[v]; if(S==nd||u<=lim) g[v]=1; S+=f[v]; } } for(int u=1;u<=n;u++) remg1[u]=gr[u]; bd(1,1,n); } inline void trs_lca(int d){ } inline void trs(){ int nowlca=n+1; for(int d=n;d>=1;d--){ while(nowlca>=2&&nowlca-1>=d-b+1){ nowlca--; trs_lca(nowlca); } for(int x:P[d]){ node A=gt(x),B=gt(fab[x]); if(A.g-B.g)h[x]=1; uph(x); } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("SS.in","r",stdin); // freopen("SS.out","w",stdout); return 0; } /* */