#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];
int dp3[N][N],dp4[N][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]=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 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],dp3D[N][15];
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 dfs2(int u,int d){
int &ret=dp4[u][d];
if(ret) return ret;
ret=u;
if(d>=1) for(int v: c[u]) ret=min(ret,dfs2(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(auto [u,v]: ev[D]) T.upd(1,1,n,in[u],dp[v][0]);
for(int u: dL[D]){
for(int i=0;i<(int)dA[u].size();i++){
int v=dA[u][i];
int val=1e9;
{
int 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)];
assert(dep[v]-dep[ww]==b);
}
if(in[ww]<=in[w]-1) val=min(val,T.qry(1,1,n,in[ww],in[w]-1));
val=min(val,dp[w][e]);
int d=dep[v]-dep[w];
if(d<b){
if((int)dp3D[w][b-d].size()!=(int)c[w].size()){
for(int j=0;j<(int)c[w].size();j++) dp3D[w][b-d].insert(-dfs1(c[w][j],b-d-1));
}
if(e) dp3D[w][b-d].erase(-dfs1(c[w][e-1],b-d-1));
if(dp3D[w][b-d].size()){
val=min(val,-dp3D[w][b-d].top());
}
if(e) dp3D[w][b-d].insert(-dfs1(c[w][e-1],b-d-1));
}
e=q[ww];
w=p[ww];
}
}
dp2[u][i]=val;
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) ret=min(ret,dfs2(c[u][i],b-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]);
}
}
}
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 |
4700 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
41560 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
19292 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Runtime error |
77 ms |
41560 KB |
Execution killed with signal 11 |
| 7 |
Halted |
0 ms |
0 KB |
- |
