#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>;
const int N=300005;
int n,r,a,b,dep[N],p[N],q[N],L[N],pA[N],subA[N];
vector<int> dp[N],dp2[N];
int dp3[N][15],dp4[N][15];
vector<int> g[N],c[N],dA[N],idxsubA[N];
void dfs0(int u){
L[dep[u]]=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);
}
int idx=0;
for(int v: g[u]) if(p[u]!=v){
dep[v]=dep[u]+1;
p[v]=u;
q[v]=++idx;
c[u].push_back(v);
dfs0(v);
}
}
int dfs1(int u,int d);
int dfs2(int u,int d);
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 Get(int u,int k){
int &ret=dp[u][k];
if(ret) return ret;
if((int)dp2C[u].size()!=(int)dA[u].size()){
for(int i=0;i<(int)dA[u].size();i++){
int v=dA[u][i];
int val=dfs1(v,b),w=v,d=0,e=0;
while(d<b){
e=q[w];
w=p[w];
d++;
val=min(val,Get(w,e));
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((int)c[w].size()>1){
dp3D[w][b-d].erase(-dfs1(c[w][e-1],b-d-1));
val=min(val,-dp3D[w][b-d].top());
dp3D[w][b-d].insert(-dfs1(c[w][e-1],b-d-1));
}
}
}
dp2[u][i]=val;
dp2C[u].insert(dp2[u][i]);
}
}
if(dA[u].empty()||(k&&dA[u].size()==idxsubA[c[u][k-1]].size())){
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]);
}
}
debug(u,k,ret);
return ret;
}
int dfs1(int u,int d){
int &ret=dp3[u][d];
if(ret) return ret;
ret=Get(u,0);
if(d>=1) for(int v: c[u]) ret=min(ret,dfs1(v,d-1));
debug(u,d,0,ret);
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));
debug(u,d,1,ret);
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 i=1;i<=n;i++){
dp[i].resize(c[i].size()+1);
dp2[i].resize(dA[i].size());
}
cout<<Get(r,0);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
343120 KB |
Output is correct |
2 |
Correct |
115 ms |
343192 KB |
Output is correct |
3 |
Correct |
111 ms |
343108 KB |
Output is correct |
4 |
Correct |
114 ms |
343140 KB |
Output is correct |
5 |
Correct |
113 ms |
343120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1066 ms |
537368 KB |
Output is correct |
2 |
Correct |
662 ms |
495632 KB |
Output is correct |
3 |
Correct |
992 ms |
601680 KB |
Output is correct |
4 |
Execution timed out |
6068 ms |
459708 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
343444 KB |
Output is correct |
2 |
Correct |
115 ms |
343396 KB |
Output is correct |
3 |
Correct |
115 ms |
343380 KB |
Output is correct |
4 |
Correct |
115 ms |
343368 KB |
Output is correct |
5 |
Correct |
120 ms |
343380 KB |
Output is correct |
6 |
Correct |
126 ms |
343432 KB |
Output is correct |
7 |
Correct |
135 ms |
343376 KB |
Output is correct |
8 |
Correct |
116 ms |
343376 KB |
Output is correct |
9 |
Correct |
124 ms |
343124 KB |
Output is correct |
10 |
Correct |
108 ms |
343376 KB |
Output is correct |
11 |
Correct |
110 ms |
343544 KB |
Output is correct |
12 |
Correct |
108 ms |
343124 KB |
Output is correct |
13 |
Correct |
125 ms |
343288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
343444 KB |
Output is correct |
2 |
Correct |
115 ms |
343396 KB |
Output is correct |
3 |
Correct |
115 ms |
343380 KB |
Output is correct |
4 |
Correct |
115 ms |
343368 KB |
Output is correct |
5 |
Correct |
120 ms |
343380 KB |
Output is correct |
6 |
Correct |
126 ms |
343432 KB |
Output is correct |
7 |
Correct |
135 ms |
343376 KB |
Output is correct |
8 |
Correct |
116 ms |
343376 KB |
Output is correct |
9 |
Correct |
124 ms |
343124 KB |
Output is correct |
10 |
Correct |
108 ms |
343376 KB |
Output is correct |
11 |
Correct |
110 ms |
343544 KB |
Output is correct |
12 |
Correct |
108 ms |
343124 KB |
Output is correct |
13 |
Correct |
125 ms |
343288 KB |
Output is correct |
14 |
Correct |
115 ms |
344112 KB |
Output is correct |
15 |
Correct |
115 ms |
344148 KB |
Output is correct |
16 |
Correct |
130 ms |
344032 KB |
Output is correct |
17 |
Correct |
117 ms |
344144 KB |
Output is correct |
18 |
Correct |
114 ms |
344144 KB |
Output is correct |
19 |
Correct |
119 ms |
343972 KB |
Output is correct |
20 |
Correct |
116 ms |
344140 KB |
Output is correct |
21 |
Correct |
119 ms |
343740 KB |
Output is correct |
22 |
Correct |
113 ms |
343108 KB |
Output is correct |
23 |
Correct |
123 ms |
344768 KB |
Output is correct |
24 |
Correct |
126 ms |
344272 KB |
Output is correct |
25 |
Incorrect |
123 ms |
345108 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
245 ms |
372052 KB |
Output is correct |
2 |
Correct |
236 ms |
373972 KB |
Output is correct |
3 |
Correct |
218 ms |
372064 KB |
Output is correct |
4 |
Correct |
216 ms |
373172 KB |
Output is correct |
5 |
Correct |
216 ms |
370180 KB |
Output is correct |
6 |
Correct |
204 ms |
371144 KB |
Output is correct |
7 |
Correct |
244 ms |
375892 KB |
Output is correct |
8 |
Correct |
148 ms |
358736 KB |
Output is correct |
9 |
Correct |
299 ms |
381784 KB |
Output is correct |
10 |
Correct |
167 ms |
366420 KB |
Output is correct |
11 |
Correct |
159 ms |
352692 KB |
Output is correct |
12 |
Correct |
148 ms |
358228 KB |
Output is correct |
13 |
Correct |
114 ms |
343200 KB |
Output is correct |
14 |
Correct |
114 ms |
343120 KB |
Output is correct |
15 |
Correct |
293 ms |
376640 KB |
Output is correct |
16 |
Execution timed out |
6044 ms |
366384 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
343444 KB |
Output is correct |
2 |
Correct |
115 ms |
343396 KB |
Output is correct |
3 |
Correct |
115 ms |
343380 KB |
Output is correct |
4 |
Correct |
115 ms |
343368 KB |
Output is correct |
5 |
Correct |
120 ms |
343380 KB |
Output is correct |
6 |
Correct |
126 ms |
343432 KB |
Output is correct |
7 |
Correct |
135 ms |
343376 KB |
Output is correct |
8 |
Correct |
116 ms |
343376 KB |
Output is correct |
9 |
Correct |
124 ms |
343124 KB |
Output is correct |
10 |
Correct |
108 ms |
343376 KB |
Output is correct |
11 |
Correct |
110 ms |
343544 KB |
Output is correct |
12 |
Correct |
108 ms |
343124 KB |
Output is correct |
13 |
Correct |
125 ms |
343288 KB |
Output is correct |
14 |
Correct |
115 ms |
344112 KB |
Output is correct |
15 |
Correct |
115 ms |
344148 KB |
Output is correct |
16 |
Correct |
130 ms |
344032 KB |
Output is correct |
17 |
Correct |
117 ms |
344144 KB |
Output is correct |
18 |
Correct |
114 ms |
344144 KB |
Output is correct |
19 |
Correct |
119 ms |
343972 KB |
Output is correct |
20 |
Correct |
116 ms |
344140 KB |
Output is correct |
21 |
Correct |
119 ms |
343740 KB |
Output is correct |
22 |
Correct |
113 ms |
343108 KB |
Output is correct |
23 |
Correct |
123 ms |
344768 KB |
Output is correct |
24 |
Correct |
126 ms |
344272 KB |
Output is correct |
25 |
Incorrect |
123 ms |
345108 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
343120 KB |
Output is correct |
2 |
Correct |
115 ms |
343192 KB |
Output is correct |
3 |
Correct |
111 ms |
343108 KB |
Output is correct |
4 |
Correct |
114 ms |
343140 KB |
Output is correct |
5 |
Correct |
113 ms |
343120 KB |
Output is correct |
6 |
Correct |
1066 ms |
537368 KB |
Output is correct |
7 |
Correct |
662 ms |
495632 KB |
Output is correct |
8 |
Correct |
992 ms |
601680 KB |
Output is correct |
9 |
Execution timed out |
6068 ms |
459708 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |