[CEOI2017] Mousetrap
策略其实比较好想但是把式子列出来有点难。
不妨把陷阱房作为根,这样就只用把老鼠往上赶。
设起始房为 st,陷阱房为 ed。
考虑 st 是 ed 的子节点,老鼠不可能送死所以会往子节点走,而管理员的最优策略是老鼠边走边堵。
直到老鼠动不了时,设在节点 x,把 x 到 ed 路径上所有点到未脏子节点的走廊堵住然后打扫。
设 \(dp_x\) 表示从 x 走到子节点最后回到 x 的最小操作数,\(son_x\) 表示 x 的儿子数,则
\[dp_x=\sum_{y\in son_x}second \max(dp_y)+son_x
\]
因为老鼠要操作尽量大,所以首先堵 dp 值最大的,要把走的那条走廊打扫,其他堵住,所以是 \(son_x\)。
设 \(f_x\) 表示把 x 到 ed 路径上节点的子节点堵住的操作数,递推可得
\[f_x=f_fax+son_x-1+(x=st)
\]
如果 x 不为 st 那么往上走时的那条边就不用堵了。
则 x 走儿子 y 的花费为 \(f_x+dp_y\)。
st 不为 ed 儿子节点时老鼠可能向上走一段再走儿子。
二分 mid,如果花费<=mid 老鼠肯定不会走,否则需要堵住(x,y)。
老鼠在向儿子走之前每一步管理员会积累一次操作,如果当前需要堵的儿子数>操作数也是不合法的。
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
const int MAXN=1e6+5;
int n,st,ed,fa[MAXN],cnt,head[MAXN],dp[MAXN],f[MAXN],res,son[MAXN];
bool vis[MAXN];
struct ren{
int nxt,to;
}a[MAXN<<1];
void add(int x,int y){
a[++cnt].to=y;a[cnt].nxt=head[x];head[x]=cnt;
}
void dfs(int now,int F){
fa[now]=F;
for(int i=head[now];i;i=a[i].nxt){
int u=a[i].to;if(u==F) continue;dfs(u,now);
son[now]++;
}
}
void dfs1(int now,int F){
if(F) f[now]=f[F]+son[now]-1+(now==st);
int ma1=0,ma2=0;
for(int i=head[now];i;i=a[i].nxt){
int u=a[i].to;if(u==F) continue;dfs1(u,now);if(dp[u]>ma1) ma2=ma1,ma1=dp[u];else if(dp[u]>ma2) ma2=dp[u];
}
dp[now]=ma2+son[now];
}
bool check(int x){
int cz=1;
for(int now=st;now!=ed;cz++,now=fa[now]){
int tt=0;
for(int i=head[now];i;i=a[i].nxt){
int u=a[i].to;
if(vis[u]||dp[u]+f[now]<=x) continue;
tt++;cz--;
}
if(cz<0) return false;
x-=tt;
}
return x>=0;
}
int main(){
scanf("%d%d%d",&n,&ed,&st);
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);add(x,y);add(y,x);
}
dfs(ed,0);
dfs1(ed,0);
int op=st;
while(op){vis[op]=1;op=fa[op];}
int L=0,R=n-1;
while(L<=R){
int mid=(L+R)>>1;
if(check(mid)) res=mid,R=mid-1;
else L=mid+1;
}
printf("%d",res);return 0;
}