题解 P4654 【[CEOI2017]Mousetrap】
lhm_
·
2020-08-28 10:25:32
·
题解
为方便处理，把树看作有根树，将陷阱房作为树的根。
先考虑一种特殊情况，老鼠起始房间和陷阱房是相邻的，即老鼠起始房间为根节点的一个儿子。一开始老鼠的决策是不可能向上走，其只可能一路向下沿最优路线到叶子节点，直到其无法行动。管理者的决策则是在老鼠向下走时堵住沿途的一些边，直到老鼠无法行动后，再堵住老鼠所在的叶子节点到根的路径上每个点延伸出去的分叉边，然后将路径进行清理，这样老鼠就会被一路赶到根节点。考虑树形 DP ，设 f_x 为老鼠在点 x 进入 x 的子树后，将其又赶回点 x 的最小操作次数，得：
\large f_x = \underset{y \in son_x}{\text{2ndmax}}\{ f_y \} + num_x
其中 \text{2ndmax} 表示次大值，num_x 表示点 x 的儿子个数。老鼠的最优决策一定是往 f 尽可能大的点走，管理者的最优决策一定是堵住通向最大值的那条边，因此是从次大值转移过来。儿子个数是必要的操作次数，即堵住分叉边和清理边。
当老鼠起始房间和陷阱房不相邻时，一开始老鼠不一定会直接向下走，其可能会先向上跳，到达某个节点后才开始向下走，开始走后老鼠对走哪个儿子的选择取决于管理者堵边的情况。不难计算出老鼠选择完儿子后的最小操作次数，设老鼠在点 x 开始向下走，选择儿子点 y ，得：
\large\begin{aligned}
cost&=f_y+sum_x \\
sum_x&=sum_{fa_x}+num_x-1+[x=m],(x\not = root)\\
\end{aligned}
并不好处理老鼠在向上跳时管理者的决策，发现答案具有单调性，可以考虑进行二分操作次数。判定二分时，让老鼠不断向上跳，当老鼠所在的节点可以和某个儿子组成的 $cost$ 大于当前还可进行的操作次数，就需要将通向这个儿子的边堵住。当前操作次数不够用或者超过了二分的操作次数时，二分的值就判定为不合法。
```cpp
#include<bits/stdc++.h>
#define maxn 2000010
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,root,m,l,r,ans;
int fa[maxn],f[maxn],sum[maxn];
bool tag[maxn];
struct edge
{
int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
e[++edge_cnt]={to,head[from]},head[from]=edge_cnt;
}
void dfs(int x,int fath)
{
fa[x]=fath;
int son=0,mx1=0,mx2=0;
for(int i=head[x];i;i=e[i].nxt) son+=(e[i].to!=fath);
if(x!=root) sum[x]=sum[fath]+son-1+(x==m);
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fath) continue;
dfs(y,x);
if(f[y]>mx1) mx2=mx1,mx1=f[y];
else if(f[y]>mx2) mx2=f[y];
}
f[x]=mx2+son;
}
bool check(int val)
{
int cnt=1;
for(int x=m;x!=root;x=fa[x],cnt++)
{
int v=0;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(tag[y]||f[y]+sum[x]<=val) continue;
if(!cnt) return false;
v++,cnt--;
}
val-=v;
}
return val>=0;
}
int main()
{
read(n),read(root),read(m),r=2*n;
for(int i=1;i<n;++i)
{
int x,y;
read(x),read(y);
add(x,y),add(y,x);
}
dfs(root,0);
for(int i=m;i;i=fa[i]) tag[i]=true;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
return 0;
}
```