题目

• 原题地址：E2. Escape The Maze (hard version)
• 题目编号：1611E2
• 目标算法：深搜（dfs）、最短路、动态规划（dp）
• 难度评分：1900

1.题目大意

• 基本的内容和 E1 一样，只有问题不同
• 上一篇题解的链接如下：
• 问在给定的朋友中，最少几人可以拦住小 V。

2.题目分析

• 在上一题的基础上：
  1. 输出为 YES 的情况无人可拦，输出 -1；
  2. 输出为 NO 的情况只需要选出：所有无人的叶子结点中，每个结点拦住小 V 的不同的朋友个数。

3.题目代码

#include 
#define MAX 200005

using namespace std;

const int INF = 0x3f3f3f3f;
vector e[MAX];
int dis[MAX], dp[MAX];
int ans = 0;

void dfs(int u, int pre)
{
    if(u != 1)
        dp[u] = dp[pre] + 1;
    for(int v: e[u])
        if(v!=pre)
            dfs(v, u);
}

void dfs2(int u, int pre)
{
    if(dis[u] == 0) return;
    int t = INF;
    for(int v: e[u])
    {
        if(v==pre) continue;
        dfs2(v, u);
        t = min(t, dis[v]);
    }
    dis[u] = t + 1;
}

bool dfs3(int u, int pre)
{
    if(dis[u]<=dp[u])
    {
        ans++;
        return 0;
    }
    if(e[u].size()==1&&u!=1) return 1;
    bool f = 0;
    for(int v: e[u])
        if(v!=pre)
            f |= dfs3(v, u);
    return f;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, k;
        cin >> n >> k;
        for(int i=1;i<=n;i++)
        {
            dp[i] = 0;
            dis[i] = INF;
            e[i].clear();
        }

        for(int i=1;i<=k;i++)
        {
            int t;
            cin >> t;
            dis[t] = 0;
        }
        for(int i=1;i> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs(1, 0);
        dfs2(1, 0);
        if(dfs3(1, 0))
            cout << -1 << endl;
        else
            cout << ans << endl;;
        ans = 0;
    }
}

• 参考题解