题解：CF1611E2 Escape The Maze (hard version) （逃离迷宫（困难版））

· · 题解

题解：CF1611E2 Escape The Maze (hard version) （逃离迷宫（困难版））

建议先阅读这篇题解，再阅读本篇。

题意

在一棵树上，有一个人 Vald 位于点 1，他的目的是到达一个编号不是 1 的节点。
有 k 个人位于点 x_1,x_2,\cdots,x_k，他们的目的是拦截 Vald。每个人在单位时间内可以移动到相邻的点，或不移动。
如果 Vald 在某一时刻和他的朋友处在同一节点，那么 Vald 无法获胜。
如果 Vald 到达了一个编号不是 1 的叶子节点，且在中途没有遇到朋友，那么 Vald 获胜。
求在给定的朋友中，最少选多少个朋友可以让 Vald 失败，或者所有朋友都无法让他失败。

思路

在上一篇题解中讲述了求所有朋友能否拦截他的方法，此处简略带过。
用多源 BFS 求出每个点到最近的朋友的距离，然后用 DFS 求出 Vald 到每个点的距离。
如果 Vald 到一个点的距离小于朋友到这个点的距离，那么他在这个点是安全的，判断每个叶子的路径上的所有点是不是安全，如果存在一个可以安全到达的编号不是 1 的叶子节点，那么 Vald 胜利。

而在这道题中，我们换个视角，看朋友能不能胜利。
老样子，BFS 和 DFS 算出每个点是不是能抓到 Vald，如果一个点能抓到 Vald，那么他也无法到达以这个点为根的子树。
这就相当于，只要一个点能抓住，以这个点为根的子树就被这个点保护起来了，那么这个子树内的所有朋友都不需要了。
如果一个点没有被保护，且能抓到 Vald，那么这个点对应的朋友是有用的。
那么现在就有思路了， f_i 表示这个点能不能抓到 Vald。
如果一个点的父亲节点已经能抓到了，那么这个节点也无所谓了。
如果一个父亲节点不能抓到，且这个点能抓到，那么需要一个朋友蹲守在此处，此时答案增加 1。
最后，判断是不是每一个编号不是 1 的叶子结点都能抓住，然后输出答案即可。

代码

:::success[AC code]

#include<bits/stdc++.h>
using namespace std;
int t,n,k,x[200010],b[200010],ans[200010],ans1[200010],f[200010],cnt;
vector<int> a[200010];
queue<int> que;
void bfs()//多源 BFS
{
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        for(int i=0;i<a[now].size();i++)
        {
            if(!b[a[now][i]])
            {
                b[a[now][i]]=1;
                ans[a[now][i]]=ans[now]+1;
                que.push(a[now][i]);
            }
        }
    }
}
void dfs(int x,int fa)
{
    if(!f[fa] && ans[x]<=ans1[x])//如果父节点并没有被保护但这个节点能抓到 Vald 那么可行。
    {
        cnt++;
    }
    f[x]=f[fa] | ans[x]<=ans1[x];//更新这个点能否抓到 Vald。
    for(int i=0;i<a[x].size();i++)
    {
        if(a[x][i]==fa)
        {
            continue;
        }
        ans1[a[x][i]]=ans1[x]+1;
        dfs(a[x][i],x);
    }
}
int main()
{
    cin>>t;
    while(t--)
    {
        cnt=0;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            a[i].clear();
            b[i]=ans[i]=ans1[i]=f[i]=0;
        }
        for(int i=1;i<=k;i++)
        {
            cin>>x[i];
            que.push(x[i]);
            b[x[i]]=1;
        }
        for(int i=1;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            a[x].push_back(y);
            a[y].push_back(x);
        }
        bfs();
        dfs(1,0);
        bool f1=true;
        for(int i=2;i<=n;i++)
        {
            if(a[i].size()==1 && !f[i])//如果有叶子结点没有覆盖到那就不行。
            {
                f1=false;
            }
        }
        if(f1)
        {
            cout<<cnt<<endl;
        }
        else
        {
            cout<<-1<<endl;
        }
    }
    return 0;
}//by Ruanqiming

::: 码风较丑，请见谅……

总结

相较于上一题来说，此题确实会难一点，要找到一个点不能到达，那么整个子树就无法到达的性质，上一题的思路不难，这题需要想想。