#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;
const int MAX_N=300010;
const int BN=20;
int n,root,m1,m2;
vint edge[MAX_N];
int sz[MAX_N],lock[MAX_N],cp[MAX_N]; //cent data
int dfsi[MAX_N],dfso[MAX_N],dfsr[MAX_N]; //dfs order data
int depth[MAX_N],ac[MAX_N][BN]; //lca data
vint depv[MAX_N]; //bfs order data
queue<pii> qc; //queue for cent
int bfso[MAX_N][BN]; //for cent update
int pa[MAX_N],pi[MAX_N],cc[MAX_N]; //for parent,child calc
int val[MAX_N];vint valc[MAX_N]; //for dt ans
int dseg[MAX_N<<2],lmv[MAX_N]; //for last move
void dfs_init(int v,int p,int &c)
{
depth[v]=depth[p]+1;
ac[v][0]=pa[v]=p;
for(int i=1;i<BN;i++)
ac[v][i]=ac[ac[v][i-1]][i-1];
depv[depth[v]].push_back(c);
dfsr[c]=v;
dfsi[v]=c++;
for(auto v0 : edge[v])
if(v0!=p)
pi[v0]=cc[v]++;
for(auto v0 : edge[v])
if(v0!=p)
dfs_init(v0,v,c);
dfso[v]=c;
}
int lca(int u,int v)
{
if(depth[u]>depth[v])swap(u,v);
for(int i=BN-1;i>=0;i--)
if(depth[ac[v][i]]>=depth[u])
v=ac[v][i];
if(v==u)return v;
for(int i=BN-1;i>=0;i--)
if(ac[v][i]!=ac[u][i])
{
v=ac[v][i];
u=ac[u][i];
}
return ac[v][0];
}
int lcad(int u,int v)
{
return depth[u]+depth[v]-depth[lca(u,v)]*2;
}
int lcap(int v,int p)
{
for(int i=BN-1;i>=0;i--)
if(depth[ac[v][i]]>depth[p])
v=ac[v][i];
return v;
}
int fillsz(int v,int p)
{
sz[v]=1;
for(auto v0 : edge[v])
if(v0!=p && !lock[v0])
sz[v]+=fillsz(v0,v);
return sz[v];
}
int findct(int v,int p,int h)
{
for(auto v0 : edge[v])
if(v0!=p && !lock[v0] && sz[v0]>h)
return findct(v0,v,h);
return v;
}
struct Cent
{
int ct,csz,cd;
vint vert;
int md;
vint dist;
vint seg;
void update_(int i,int s,int e,int x,int v)
{
if(s>x || e<=x)return;
if(s==x && x+1==e)
{
seg[i]=v;
return;
}
update_(i<<1,s,(s+e)>>1,x,v);
update_(i<<1|1,(s+e)>>1,e,x,v);
seg[i]=min(seg[i<<1],seg[i<<1|1]);
}
int find_(int i,int s,int e,int l,int r)
{
if(s>=r || e<=l)return MAX_N;
if(l<=s && e<=r)return seg[i];
return min(find_(i<<1,s,(s+e)>>1,l,r),find_(i<<1|1,(s+e)>>1,e,l,r));
}
void updateout(int x,int v)
{
update_(1,0,csz,x,v);
}
int findout(int d)
{
return find_(1,0,csz,0,dist[min(d,md)]);
}
void init_(int ct_,int cd_)
{
ct=ct_;cd=cd_;
fillsz(ct,0);
csz=sz[ct];
qc.push({ct,0});
lock[ct]=2;
while(!qc.empty())
{
pii p=qc.front();qc.pop();
bfso[p.first][cd]=vert.size();
vert.push_back(p.first);
if(dist.size()<=p.second)dist.push_back(1);
else dist[p.second]++;
for(auto v : edge[p.first])
if(!lock[v])
{
lock[v]=2;
qc.push({v,p.second+1});
}
}
for(auto v : vert)lock[v]=0;
md=dist.size()-1;
for(int i=0;i<md;i++)dist[i+1]+=dist[i];
seg.resize(csz<<2);
}
};
Cent cent[MAX_N];
void cent_init(int v,int p,int d)
{
v=findct(v,0,fillsz(v,0)/2);
cp[v]=p;
cent[v].init_(v,d);
lock[v]=1;
for(auto v0 : edge[v])
if(!lock[v0])
cent_init(v0,v,d+1);
}
void updatein(int v,int vv)
{
int ct=v;
while(ct)
{
cent[ct].updateout(bfso[v][cent[ct].cd],vv);
ct=cp[ct];
}
}
int findin(int v,int d)
{
int ret=MAX_N;
int ct=v;
while(ct)
{
int d2=d-lcad(v,ct);
if(d2<0)break;
ret=min(ret,cent[ct].findout(d2));
ct=cp[ct];
}
return ret;
}
void updated(int i,int s,int e,int x,int v)
{
if(s>x || e<=x)return;
if(s==x && x+1==e)
{
dseg[i]=v;
return;
}
updated(i<<1,s,(s+e)>>1,x,v);
updated(i<<1|1,(s+e)>>1,e,x,v);
dseg[i]=min(dseg[i<<1],dseg[i<<1|1]);
}
int findd(int i,int s,int e,int l,int r)
{
if(s>=r || e<=l)return MAX_N;
if(l<=s && e<=r)return dseg[i];
return min(findd(i<<1,s,(s+e)>>1,l,r),findd(i<<1|1,(s+e)>>1,e,l,r));
}
void lastmove_init()
{
for(int i=0;i<n;i++)
updated(1,0,n,i,MAX_N);
for(int d=MAX_N-1;d>=1;d--)
{
for(auto i : depv[d])
{
int v=dfsr[i];
updated(1,0,n,i,v);
lmv[v]=findd(1,0,n,dfsi[v],dfso[v]);
}
if(d+m2>=MAX_N)continue;
for(auto i : depv[d+m2])
updated(1,0,n,i,MAX_N);
}
}
void calc(int v)
{
int d=depth[v],d2=depth[v]+m1,li,ri;
if(d2>=MAX_N)
li=ri=0;
else
{
li=lower_bound(depv[d2].begin(),depv[d2].end(),dfsi[v])-depv[d2].begin();
ri=lower_bound(depv[d2].begin(),depv[d2].end(),dfso[v])-depv[d2].begin();
}
vint ov(cc[v],-1);
for(int i=li;i<ri;i++)
{
int c=dfsr[depv[d2][i]];
int v0=lcap(c,v);
ov[pi[v0]]=max(ov[pi[v0]],findin(c,m2));
if(i!=ri-1)
{
int c2=dfsr[depv[d2][i+1]];
int l=lca(c,c2);
if(l!=v)
updatein(l,valc[l][pi[lcap(c2,l)]]);
}
}
for(int i=ri-2;i>=li;i--)
{
int c=dfsr[depv[d2][i]];
int c2=dfsr[depv[d2][i+1]];
int l=lca(c,c2);
if(l!=v)
updatein(l,valc[l][pi[lcap(c,l)]]);
}
int pv=-1,plm=v;
vint lv(cc[v],-1),rv(cc[v],-1);
vint olm(cc[v],MAX_N);
vint llm(cc[v],MAX_N),rlm(cc[v],MAX_N);
for(auto v0 : edge[v])
if(v0!=pa[v])
olm[pi[v0]]=lmv[v0];
for(int i=0;i<cc[v];i++)
{
pv=max(pv,ov[i]);
plm=min(plm,olm[i]);
}
for(int i=0;i<cc[v]-1;i++)
{
lv[i+1]=max(lv[i],ov[i]);
llm[i+1]=min(llm[i],olm[i]);
}
for(int i=cc[v]-1;i>=1;i--)
{
rv[i-1]=max(rv[i],ov[i]);
rlm[i-1]=min(rlm[i],olm[i]);
}
if(pv==-1)pv=plm;
val[v]=pv;
valc[v].resize(cc[v]);
for(int i=0;i<cc[v];i++)
{
int cv=max(lv[i],rv[i]);
if(cv==-1)cv=min(v,min(llm[i],rlm[i]));
valc[v][i]=cv;
}
}
void solve()
{
for(int d=MAX_N-1;d>=1;d--)
{
for(auto i : depv[d])
{
int v=dfsr[i];
calc(v);
if(valc[v].empty())updatein(v,val[v]);
else updatein(v,valc[v][0]);
}
if(d+m1-1>=MAX_N)continue;
for(auto i : depv[d+m1-1])
{
int v=dfsr[i];
updatein(v,val[v]);
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> root >> m1 >> m2;
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
if(m1<=m2)
{
cout << 1;
return 0;
}
int idx=0;
dfs_init(root,0,idx);
cent_init(root,0,0);
lastmove_init();
solve();
cout << val[root];
return 0;
}
Compilation message
Main.cpp: In member function 'void Cent::init_(int, int)':
Main.cpp:134:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
134 | if(dist.size()<=p.second)dist.push_back(1);
| ~~~~~~~~~~~^~~~~~~~~~
Main.cpp: In function 'void calc(int)':
Main.cpp:226:9: warning: unused variable 'd' [-Wunused-variable]
226 | int d=depth[v],d2=depth[v]+m1,li,ri;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
67664 KB |
Output is correct |
| 2 |
Correct |
71 ms |
68688 KB |
Output is correct |
| 3 |
Correct |
64 ms |
68948 KB |
Output is correct |
| 4 |
Correct |
66 ms |
69344 KB |
Output is correct |
| 5 |
Correct |
7 ms |
55896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2131 ms |
307152 KB |
Output is correct |
| 2 |
Incorrect |
2139 ms |
307068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
68188 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
68424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
68188 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
68424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
420 ms |
114016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
68188 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
68424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
67664 KB |
Output is correct |
| 2 |
Correct |
71 ms |
68688 KB |
Output is correct |
| 3 |
Correct |
64 ms |
68948 KB |
Output is correct |
| 4 |
Correct |
66 ms |
69344 KB |
Output is correct |
| 5 |
Correct |
7 ms |
55896 KB |
Output is correct |
| 6 |
Correct |
2131 ms |
307152 KB |
Output is correct |
| 7 |
Incorrect |
2139 ms |
307068 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
