题解

思路概述

• 迷宫是一棵树，老鼠只能顺着干净且未被封堵的边移动；管理者每一步可以封死/擦净一条边。核心在于主干路径——从老鼠起点 $s$ 到陷阱 $t$ 的简单路径。只要能让老鼠沿着这条路径被迫向 $t$ 移动，并保证它不会有机会钻入侧枝，就能得到最优策略。
• 先任选 $t$ 为根，对整棵树做一遍 DFS。对每个结点，我们统计它在树上的“侧枝数量”并递推两个量：
  1. sum[x]：在把老鼠从 $s$ 赶到结点 $x$ 的过程中，已经必须处理的侧枝数量偏移；
  2. f[x]：若老鼠进入以 $x$ 为根的子树，最坏情况下还需要多少步才能把它逼出该子树。这可以通过对子结点的 f 值排序、取前两大来转移——管理者可以先封住较小的子树，把老鼠往成本更高的子树逼。
• 把 $s$ 到 $t$ 的路径标记出来后，二分答案 $T$。给定一个候选时间，沿主干从 $s$ 向 $t$ 模拟：当前在结点 $u$ 时，检查所有未在主干上的子树，若 f[child] + sum[u] > T，说明在时限内无论如何无法先封死这棵子树从而继续押送老鼠，判定失败。否则把这些子树记入已经消耗的操作次数，继续前进。若最终抵达 $t$ 并且剩余步数不为负，则说明 $T$ 可行。

实现细节

• 第一次 DFS 以 $t$ 为根，求出父亲数组、sum 与 f。sum 在沿父边传播时累加，表示到当前结点之前已经额外消耗的封边次数。f 的转移公式 f[x] = 第二大的子树代价 + 当前可用出口数 正好对应管理者需要留出一条出口把老鼠赶向父亲的策略。
• 检查函数按主干路径从 $s$ 走到 $t$。cnt 表示当前手里尚未被消耗的“安全出口”数，val 表示还允许的操作次数；遇到无法在时限内封掉的子树就扣减 cnt，若不足则失败；每向前一步都会扣掉本层处理侧枝所花的操作。
• 由于主干长度至多 $O(n)$，而二分的上界是 $O(n)$，整体做法可行。

复杂度

预处理 DFS 为 $O(n)$，二分时每次检验沿主干扫描一次，因此总时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int f[N],sum[N],fa[N];
int e[N],ls[N],nx[N],em;
bool note[N];
int n,st,rt;
void insert(int x,int y)
{
	e[++em]=y,nx[em]=ls[x],ls[x]=em; return ;
}
void dfs(int x)
{
	int mx1=0,mx2=0,ss=0;
	for(int i=ls[x];i;i=nx[i]){
		if(fa[x]==e[i]) continue ; ss++;
	}
	if(x==st) sum[x]=sum[x]+ss;
	else sum[x]=sum[x]+ss-1;
	for(int i=ls[x];i;i=nx[i]){
		if(fa[x]==e[i]) continue ;
		sum[e[i]]=sum[e[i]]+sum[x];
 		fa[e[i]]=x; dfs(e[i]); 
		if(f[e[i]]>mx1) mx2=mx1,mx1=f[e[i]];
		else if(f[e[i]]>mx2) mx2=f[e[i]];
	}
	f[x]=mx2+ss;
//	cout<<x<<" "<<fa[x]<<" "<<f[x]<<" "<<ss<<" "<<mx2<<" "<<sum[x]<<endl;
	return ; 
}
bool check(int x)
{
	int val=x,cnt=1,ss=0;
	for(int i=st;i!=rt;i=fa[i]){
		for(int j=ls[i];j;j=nx[j]){
			if(fa[i]==e[j]||note[e[j]]||f[e[j]]+sum[i]<=val) continue ;
			if(!cnt) return false; cnt--; ss++;
		}
		cnt++; val=val-ss; ss=0;
	}
	if(val>=0) return true;
	else return false;
}
int main()
{
//	freopen("mousetrap.in","r",stdin);
	scanf("%d%d%d",&n,&rt,&st);
	for(int i=1;i<n;i++){
		int x,y; scanf("%d%d",&x,&y);
		insert(x,y); insert(y,x);
	}
	dfs(rt);
	for(int i=st;i!=rt;i=fa[i]) note[i]=true;
	int l=0,r=n*2,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(!check(mid)) l=mid+1;
		else r=mid-1;
	}
	printf("%d",l);
	return 0;
}