【CF1611】E. Escape The Maze（easy+hard）

E1题目链接：https://codeforces.com/contest/1611/problem/E1
E2题目链接：https://codeforces.com/contest/1611/problem/E2

分析

我们定义一个点叫做安全点，即走到这个点上即可到达安全的叶子节点（不会被朋友逮到）；朋友初始站的点叫朋友点，否则叫非朋友点；$deep[i]$表示第$i$号点的深度，$md[i]$表示在第$i$号点下面距离$i$最近的朋友点的深度。

很明显若一个点是叶子节点，同时它是非朋友点，那么它就是一个安全点；同样很明显若一个点是朋友点，那么它以及它下方的点一定不是安全点。我们可以将安全点的状态转移向它的父亲点进行转移。
如何确定一个非叶子非朋友节点$i$是否是安全点呢？若$i$的孩子节点中有安全点，同时
在第$i$号点下面距离$i$最近的朋友点的距离比该点到$1$号点的距离大（$deep[i]?1<md[i]?deep[i]$），也就是朋友抓不到Vlad，那么$i$号点就是一个安全点。

对于E1，只要判断最终$1$号点是不是安全点即可。
对于E2，如果$1$号点不是安全点，那么想一下，我们如果将所有的朋友点都尽量往上移动，移到最极限的位置（即刚好和Vlad碰到），然后dfs搜索到朋友点就$ans+1$，并且不必再遍历下去。我们可以利用$md$数组来实现这个过程，即搜索到一个点$i$满足$deep[i]?1\ge md[i]?deep[i]$，就$ans+1$，并且不必再遍历下去。

具体看代码

代码

E1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define fi first
#define se second
#define lson (k << 1)
#define rson (k << 1 | 1)const ll LINF = 1e18;
const int INF = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const ll P = 1e9 + 7;
const double eps = 1e-7;int n, k;
int f[N], safe[N], deep[N], md[N];
vector<int> g[N];void dfs(int u, int fa)
{
    deep[u] = deep[fa] + 1;if(f[u]){
    md[u] = min(md[u], deep[u]);return;}if(g[u].size() == 1 && u != 1){
    safe[u] = 1;return;}int ifsafe = 0, mn = INF;for(int i=0,v;i<g[u].size();i++){
    v = g[u][i];if(v == fa) continue;dfs(v, u);md[u] = min(md[u], md[v]);if(safe[v]) ifsafe = 1;}if(ifsafe && deep[u] - 1 < md[u] - deep[u]) safe[u] = 1;
}int main()
{
    int T = 1;scanf("%d",&T);while(T--){
    scanf("%d%d",&n,&k);for(int i=0;i<=n;i++) g[i].clear(), f[i] = deep[i] = safe[i] = 0, md[i] = INF;for(int i=1,x;i<=k;i++){
    scanf("%d",&x);f[x] = 1;}for(int i=1,u,v;i<n;i++){
    scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);if(safe[1]) printf("YES\n");else printf("NO\n");}return 0;
}

E2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define fi first
#define se second
#define lson (k << 1)
#define rson (k << 1 | 1)const ll LINF = 1e18;
const int INF = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const ll P = 1e9 + 7;
const double eps = 1e-7;int n, k, ans;
int f[N], safe[N], deep[N], md[N];
vector<int> g[N];void dfs(int u, int fa)
{
    deep[u] = deep[fa] + 1;if(f[u]){
    md[u] = min(md[u], deep[u]);return;}if(g[u].size() == 1 && u != 1){
    safe[u] = 1;return;}int ifsafe = 0, mn = INF;for(int i=0,v;i<g[u].size();i++){
    v = g[u][i];if(v == fa) continue;dfs(v, u);md[u] = min(md[u], md[v]);if(safe[v]) ifsafe = 1;}if(ifsafe && deep[u] - 1 < md[u] - deep[u]) safe[u] = 1;
}void dfs2(int u, int fa)
{
    if(deep[u] - 1 >= md[u] - deep[u]){
    ans++;return;}for(int i=0,v;i<g[u].size();i++){
    v = g[u][i];if(v == fa) continue;dfs2(v, u);}
}int main()
{
    int T = 1;scanf("%d",&T);while(T--){
    ans = 0;scanf("%d%d",&n,&k);for(int i=0;i<=n;i++) g[i].clear(), f[i] = deep[i] = safe[i] = 0, md[i] = INF;for(int i=1,x;i<=k;i++){
    scanf("%d",&x);f[x] = 1;}for(int i=1,u,v;i<n;i++){
    scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);if(safe[1]) printf("-1\n");else{
    dfs2(1, 0);printf("%d\n",ans);}}return 0;
}