#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
using tii=array<int,3>;
using ti4=array<int,4>;
const int N=3005;
int n,r,a,b,dep[N],p[N],q[N],L[N],pA[N],subA[N];
int sz[N],in[N],inv[N],out[N],C,ctop[N];
vector<int> dp[N],dp2[N];
set<pii> S[2][N];
vector<int> g[N],c[N],dL[N];
vector<int> dA[N],idxsubA[N];
vector<int> up[N],invup[N];
vector<pii> ev[N];
vector<ti4> qry[N];
struct SEG{
int T[2*N];
void init(int nd,int l,int r){
T[nd]=(int)1e9;
if(l==r) return;
int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
init(ln,l,m); init(rn,m+1,r);
}
void upd(int nd,int l,int r,int x,int v){
T[nd]=min(T[nd],v);
if(l==r) return;
int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
if(x<=m) upd(ln,l,m,x,v);
else upd(rn,m+1,r,x,v);
}
int qry(int nd,int l,int r,int s,int e){
if(r<s||e<l) return (int)1e9;
if(s<=l&&r<=e) return T[nd];
int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
return min(qry(ln,l,m,s,e),qry(rn,m+1,r,s,e));
}
}T;
void dfs0(int u){
L[dep[u]]=u;
dL[dep[u]].push_back(u);
if(dep[u]>=a){
pA[u]=L[dep[u]-a];
subA[u]=L[dep[u]-a+1];
idxsubA[subA[u]].push_back(dA[pA[u]].size());
dA[pA[u]].push_back(u);
}
sz[u]=1;
for(int v: g[u]) if(p[u]!=v){
dep[v]=dep[u]+1;
p[v]=u;
c[u].push_back(v);
dfs0(v);
sz[u]+=sz[v];
}
}
void dfsH(int u,int t){
in[u]=++C;
inv[in[u]]=u;
ctop[u]=t;
int idx=0;
for(int v: c[u]){
q[v]=++idx;
if(v==c[u][0]) dfsH(v,t);
else dfsH(v,v);
}
out[u]=C;
}
struct ErasableSet{
priority_queue<int> pq1,pq2;
void insert(int x){
pq1.push(x);
}
void erase(int x){
pq2.push(x);
}
int top(){
while(pq2.size()&&pq1.top()==pq2.top()){
pq1.pop();
pq2.pop();
}
return pq1.top();
}
int size(){
return pq1.size()-pq2.size();
}
}dp2C[N];
void ins(int c,int u,pii p){
auto iter=S[c][u].lower_bound(p);
while(iter!=S[c][u].end()&&p[1]<=(*iter)[1]) iter=S[c][u].erase(iter);
if(iter!=S[c][u].begin()){
iter--;
if((*iter)[1]<=p[1]) return;
}
S[c][u].insert(p);
}
void mrg(int c,int u,int v){
if(S[c][u].size()<S[c][v].size()) swap(S[c][u],S[c][v]);
for(pii p: S[c][v]) ins(c,u,p);
}
int dp3[N][N];
int dfs1(int u,int d){
int &ret=dp3[u][d];
if(ret) return ret;
ret=dp[u][0];
if(d>=1) for(int v: c[u]) ret=min(ret,dfs1(v,d-1));
return ret;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>r>>a>>b;
if(a<=b){
cout<<"1\n";
return 0;
}
for(int u,v,i=1;i<n;i++){
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs0(r);
for(int u=1;u<=n;u++){
for(int &v: c[u]) if(sz[v]>sz[c[u][0]]) swap(v,c[u][0]);
}
dfsH(r,r);
for(int i=1;i<=n;i++){
dp[i].resize(c[i].size()+1);
dp2[i].resize(dA[i].size());
}
for(int i=1;i<=n;i++){
int u=i;
while(u){
if(dep[i]-dep[u]>b) break;
if(u!=i){
up[i].push_back(u);
invup[u].push_back(i);
if(dep[u]-a+b-(dep[i]-dep[u])>=0) ev[dep[u]-a+b-(dep[i]-dep[u])].push_back({i,u});
}
u=p[ctop[u]];
}
}
T.init(1,1,n);
for(int D=n;D>=0;D--){
for(int u: dL[D]){
for(int i=0;i<(int)dA[u].size();i++){
int v=dA[u][i],w=v,e=0;
dp2[u][i]=(int)1e9;
while(w){
if(dep[v]-dep[w]>b) break;
int ww=ctop[w];
if(dep[v]-dep[ww]>b) ww=inv[in[ww]+(dep[v]-dep[ww]-b)];
int d=dep[v]-dep[w];
if(d<b) qry[w].push_back({e,b-d,u,i});
e=q[ww];
w=p[ww];
}
}
}
}
for(int D=n;D>=0;D--){
for(auto [u,v]: ev[D]) T.upd(1,1,n,in[v],dp[u][0]);
for(int u: dL[D]){
for(int i=0;i<(int)dA[u].size();i++){
int v=dA[u][i];
int &ret=dp2[u][i],w=v,e=0;
while(w){
if(dep[v]-dep[w]>b) break;
int ww=ctop[w];
if(dep[v]-dep[ww]>b) ww=inv[in[ww]+(dep[v]-dep[ww]-b)];
if(in[ww]<=in[w]-1) ret=min(ret,T.qry(1,1,n,in[ww],in[w]-1));
ret=min(ret,dp[w][e]);
e=q[ww];
w=p[ww];
}
dp2C[u].insert(dp2[u][i]);
}
for(int k=0;k<=(int)c[u].size();k++){
int &ret=dp[u][k];
if(dA[u].empty()||(k&&dA[u].size()==idxsubA[c[u][k-1]].size())){
if(k&&idxsubA[c[u][k-1]].empty()) ret=dp[u][0];
else{
ret=u;
for(int i=0;i<(int)c[u].size();i++) if(i+1!=k){
auto iter=S[0][c[u][i]].lower_bound({dep[u]+b,(int)1e9});
iter--;
ret=min(ret,(*iter)[1]);
}
}
} else{
if(k){
for(int i: idxsubA[c[u][k-1]]){
dp2C[u].erase(dp2[u][i]);
}
}
ret=dp2C[u].top();
if(k){
for(int i: idxsubA[c[u][k-1]]) dp2C[u].insert(dp2[u][i]);
}
}
}
sort(qry[u].begin(),qry[u].end());
for(auto [e,d,v,i]: qry[u]){
for(int j=0;j<(int)c[u].size();j++) if(j+1!=e){
dp2[v][i]=min(dp2[v][i],dfs1(c[u][j],d));
}
}
int prv=0;
for(auto [e,d,v,i]: qry[u]) if(e>1){
e--;
while(prv+1<e){
prv++;
set<pii> SS=S[1][c[u][prv]];
mrg(1,u,c[u][prv]);
S[1][c[u][prv]]=SS;
}
auto iter=S[1][u].lower_bound({dep[u]+d,(int)1e9});
if(iter==S[1][u].begin()) continue;
iter--;
dp2[v][i]=min(dp2[v][i],(*iter)[1]);
}
S[1][u].clear();
reverse(qry[u].begin(),qry[u].end());
prv=c[u].size();
for(auto [e,d,v,i]: qry[u]){
e--;
while(prv-1>e){
prv--;
mrg(1,u,c[u][prv]);
}
auto iter=S[1][u].lower_bound({dep[u]+d,(int)1e9});
if(iter==S[1][u].begin()) continue;
iter--;
dp2[v][i]=min(dp2[v][i],(*iter)[1]);
}
while(prv>0){
prv--;
mrg(1,u,c[u][prv]);
}
ins(0,u,{dep[u],u});
ins(1,u,{dep[u],dp[u][0]});
for(int v: c[u]) mrg(0,u,v);
if(c[u].size()) T.upd(1,1,n,in[u],dp[u][1]);
}
}
cout<<dp[r][0];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
3164 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
3164 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1628 KB |
Output is correct |
| 6 |
Runtime error |
3 ms |
3164 KB |
Execution killed with signal 11 |
| 7 |
Halted |
0 ms |
0 KB |
- |
