题解：P11516 [CCO 2024] Summer Driving
jch123
·
·
题解
题意
树上从 R 出发博弈，Alice 先手每次走恰好 A 条新边，Bob 走至多 B 条互异边；Alice 无法行动时 Bob 走至多 B 条新边结束。Alice 最大化终点编号，Bob 最小化。
思路
设 $f_u$ 为在 $u$ 且子树全新时先手能否赢；$h_v$ 为在 $fa_v$ 且禁入 $v$ 子树；$g_w$ 为刚到 $w$ 轮到后手。记 $m_u,t_u$ 为子树最浅坏点、最浅 $f=0$ 的深度。
记 $E_u$ 为子树深 $dep_u+A$ 点集。$E_u$ 空则 $f_u=[m_u>dep_u+B]$，否则 $f_u=\bigvee_{w\in E_u}g_w$；$h_v$ 即 $f_{fa_v}$ 扣去 $v$ 子树贡献（维护 $E$ 在每个儿子的大小来判断是否为空，再维护儿子 $m$ 最小与次小值）。
求 $g_w$ 时 Bob 找 $\le B$ 步内的必败态：
1. $w$ 子树内，距 $t_w-dep_w$。
2. 停在祖先 $x$（方向儿子 $y$）且 $h_y=0$。
3. 经 $x$ 拐入旁支 $z\neq y$，距 $\min_{z\neq y}t_z-2dep_x+dep_w$。
双指针将 $dep_x\ge dep_w-B$ 的祖先在线段树上对 $y$ 子树区间取 $\min$（$h_y=0$ 取 $-\infty$，否则取 $\min_{z\neq y}t_z-2dep_x$），单点查得 $val_w$，则 $g_w=[\min(t_w-dep_w,val_w+dep_w)>B]$。
总的流程是外层二分，双指针加入点，算 $E_u$ 中的 $g$，通过这个算 $t_u,f_u,h_v$。时间复杂度 $O(N\log^2 N)$。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10,M=1e9;
int fa[N],dep[N],dfn[N],sz[N],q[N],st[N],top[N],num[N],d[4*N],m[N],t[N],f[N],h[N],c[N];
vector<int> edge[N],e[N];
int n,r,A,B,tot;
bool cmp(int x,int y){return dep[x]<dep[y];}
void dfs(int u,int p)
{
fa[u]=p,dep[u]=dep[p]+1,dfn[u]=++tot,q[tot]=u,sz[u]=1,st[dep[u]]=u;
if(dep[u]>A)
e[st[dep[u]-A]].push_back(u),top[u]=st[dep[u]-A+1],num[top[u]]++;
for(int v:edge[u])
{
if(v==p) continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
void add(int &x,int &y,int z)
{
if(z<x) y=x,x=z;
else y=min(y,z);
}
void upd(int p,int l,int r,int s,int t,int k)
{
if(l>=s&&r<=t)
{
d[p]=min(d[p],k);
return;
}
int mid=(l+r)>>1;
if(s<=mid) upd(p*2,l,mid,s,t,k);
if(t>mid) upd(p*2+1,mid+1,r,s,t,k);
}
int ask(int p,int l,int r,int x)
{
if(l==r) return d[p];
int mid=(l+r)>>1,res=d[p];
if(x<=mid) return min(d[p],ask(p*2,l,mid,x));
else return min(d[p],ask(p*2+1,mid+1,r,x));
}
void insert(int u)
{
int x=M,y=M;
for(int v:edge[u])
if(v!=fa[u]) add(x,y,t[v]);
for(int v:edge[u])
{
if(v==fa[u]) continue;
int k=(t[v]==x?y:x)-2*dep[u];
if(!h[v]) k=-M;
upd(1,1,n,dfn[v],dfn[v]+sz[v]-1,k);
}
}
bool check(int mid)
{
memset(d,0x3f,sizeof(d)),memset(c,0,sizeof(c));
int j=n;
for(int i=n;i;i--)
{
//cal f[u]
int u=q[i],s=0,x=u<mid?dep[u]:M,y=M;
while(j&&dep[q[j]]>=dep[u]+A-B) insert(q[j--]);
for(int v:e[u])//dis(u,v)=A
{
int dis=min(t[v]-dep[v],ask(1,1,n,dfn[v])+dep[v]);//down
if(dis>B) s++,c[top[v]]++;//g=1
}
t[u]=M;
for(int v:edge[u])
{
if(v==fa[u]) continue;
add(x,y,m[v]),t[u]=min(t[u],t[v]);
}
m[u]=x;
if(e[u].empty()) f[u]=(m[u]>dep[u]+B);
else f[u]=(s>0);
if(!f[u]) t[u]=min(t[u],dep[u]);
for(int v:edge[u])
{
if(v==fa[u]) continue;
if(e[u].size()>num[v]) h[v]=(s>c[v]);
else h[v]=((m[v]==x?y:x)>dep[u]+B);
}
}
return f[r];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>r>>A>>B;
for(int i=1,u,v;i<n;i++)
{
cin>>u>>v;
edge[u].push_back(v),edge[v].push_back(u);
}
if(A<=B)
{
cout<<1;
return 0;
}
dfs(r,0);
sort(q+1,q+n+1,cmp);
int l=1,r=n,res=0;
while(l<=r)
{
int mid=(l+r+1)/2;
if(check(mid)) l=mid+1,res=mid;
else r=mid-1;
}
cout<<res;
return 0;
}
```