题解 CF337D 【Book of Evil】

Elma_ · 2020-08-12 09:40:42 · 题解

Description

题目链接

有 n 个点，(n-1) 条边，m 个鬼，求存在多少个点使得这个点到每个鬼的距离都不超过 d？

Solution

这里提供一种 3 次 dfs 的做法，个人感觉比树DP好写而且比较好理解。

找出在这颗树上距离最远的两只鬼，将它们的位置设为 A,B。类似于树的直径，这颗树上的其余点具有这样的性质：

如果某一个点到 A 和 B 的距离都不超过 d，那么该点到其余鬼所在点的距离也不会超过 d。

否则，如果存在某一个鬼和该点的距离超过 d，那么这个鬼所在的位置离 A,B 两点中某一点的距离大于 A,B 两点间的距离。

考虑证明这一个性质。设该点为 P，分点 P 在 A,B 两点的路径上和 P 点在 A,B 两点路径之外两种情况讨论。记 dis(x,y) 表示 x,y 两点之间的距离。

设点 P 在 A,B 路径上，设另有一只鬼在点 C。

反证法。假设 dis(P,C) > d，而根据前面性质的定义有 dis(B,P) \leq d，于是有 dis(P,C) > dis(B,P)。两边同时加上 dis(A,P) 得到:

dis(P,C) + dis(A,P) > dis(B,P) + dis(A,P) \to dis(A,C) > dis(A,B)

与 A,B 为距离最远的两只鬼矛盾。在这种情况下，该命题得证。

设点 P 在 A,B 路径之外，设另有一只鬼在点 C。

这种情况中还包含着两种小情况，同样使用反证法。

若 P,C 两点间的路径和 A,B 两点间的路径没有交点：

设有两点 U,V，U,V 之间有边连接且 U 在 A,B 路径上，V 在 P,C 路径上。

假设 dis(P,C) > d，而 dis(B,P) \leq d，于是有 dis(P,C) > dis(B,P)。两边同时减 dis(V,P) 得到:

dis(V,C) > dis(B,V)

两边同时加上dis(A,V)，得到:

dis(A,C) > dis(A,B) + 2 \times dis(U,V)

与 A,B 为距离最远的两只鬼矛盾。

若 P,C 两点间的路径和 A,B 两点间的路径有交点，设交点为 X :

假设 dis(P,C) > d，而 dis(B,P) \leq d，于是有 dis(P,C) > dis(B,P)。两边同时减 dis(X,P) 得到:

dis(X,C) > dis(X,B)

两边同时加上dis(A,X)得到:

dis(A,C) > dis(A,B)

与 A,B 为距离最远的两只鬼矛盾。该性质得证。

考虑如何找到最远的两只鬼 A,B。和树的直径相同，我们可以很自然的想到两次 dfs 的方法，第一次从任意一点出发找到离该点最远的一只鬼 A，第二次从 A 点出发找到离鬼 A 最远的一只鬼 B。

于是这个问题可以转化为找到 dis(i,A) \leq d 且 dis(i, B) \leq d 的点的个数。所以只需要求出每个点离点 A 和点 B 的距离。和点A的距离在前两次 dfs 中已经求出，所以只需要再加一次 dfs 求出每个点到点 B 的距离即可。

总共三次 dfs，最后扫一遍所有点统计答案。总时间复杂度为 O(n)。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 1000005
using namespace std;

inline int read()
{
    int x = 0, w = 1;char ch = getchar();
    while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
    while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();
    return x * w;
}

struct node
{
    int to, nxt;
}edge[maxn << 1];
int n, m, d, tot, tmp, ans;
int evil[maxn], dis1[maxn], dis2[maxn], head[maxn];

inline void add(int u, int v) { edge[++tot].nxt = head[u];edge[tot].to = v;head[u] = tot; }
inline void addedge(int u, int v) { add(u, v), add(v, u); }

void dfs1(int u, int fath, int dep)
{
    dis1[u] = dep;
    for (int i = head[u];i;i = edge[i].nxt)
    {
        int v = edge[i].to;
        if (v != fath) 
            dfs1(v, u, dep + 1);
    }
}

void dfs2(int u, int fath, int dep)
{
    dis2[u] = dep;
    for (int i = head[u];i;i = edge[i].nxt)
    {
        int v = edge[i].to;
        if (v != fath)
            dfs2(v, u, dep + 1);
    }
}

int main(void)
{
    n = read(), m = read(), d = read();
    for (int i = 1;i <= m;i++)
        evil[i] = read();
    for (int i = 1;i < n;i++)
    {
        int u = read(), v = read();
        addedge(u, v);
    }
    dfs1(1, 0, 0);
    for (int i = 1;i <= m;i++)
        if (dis1[evil[i]] > dis1[tmp]) tmp = evil[i];
    dfs1(tmp, 0, 0);tmp = 0;
    for (int i = 1;i <= m;i++)
        if (dis1[evil[i]] > dis1[tmp]) tmp = evil[i];
    dfs2(tmp, 0, 0);
    for (int i = 1;i <= n;i++)
        if (dis1[i] <= d && dis2[i] <= d) ans++;
    printf("%d\n", ans);
    return 0;
}