Book of Evil

  • 分析

    如果想要作为一个放置点，那么一个点距离一个魔鬼的最大值不能超过 d 。
    图片说明
    考虑到最大距离的产生方式——子树内部以及外部。那么可以分两步做

    1. 求出一个节点距离子树内部的鬼的最远距离从叶子结点更新到根节点
    2. 开始更新子树外的最远距离，dfs一遍，从上往下更新。

    更新方式：记录一个最大值(f)与次大值(g)，一个点要么从父节点的最远距离(dis)更新过来，要么从父节点的f或g数组更新过来。

    注意：dis数组：以i为根节点的子树外的鬼到i最最远距离。所以在统计答案的时候要dis与f都不大于d

  • 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N=1e5+10;

int n,m,d,tot;
int h[N],nex[N<<1],ver[N<<1];
int f[N],g[N],dis[N];

bool vis[N];

inline void add(int x,int y)
{
    nex[tot]=h[x];
    ver[tot]=y;
    h[x]=tot++;
}

inline void dfs(int u,int v)
{
    if(vis[u]) f[u]=0,g[u]=0;
    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(j==v) continue;

        dfs(j,u);

        if(f[j]+1>f[u])
            g[u]=f[u],f[u]=f[j]+1;
        else g[u]=max(g[u],f[j]+1);
    }
}

inline void get(int u,int v)
{
    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(j==v) continue;

        if(f[u]==f[j]+1)
            dis[j]=max(dis[u]+1,g[u]+1);
        else
            dis[j]=max(f[u]+1,dis[u]+1);

        get(j,u);
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    memset(g,-0x3f,sizeof(g));
    memset(f,-0x3f,sizeof(f));
    memset(dis,-0x3f,sizeof(dis));//刚开始凉在初始化QwQ

    scanf("%d%d%d",&n,&m,&d);
    for (int i=1,x;i<=m;i++)
    {
        scanf("%d",&x);
        vis[x]=1;
    }

    for (int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }

    dfs(1,0);get(1,0);

    int ans=0;if(f[1]<=d) ans++;
    for (int i=2;i<=n;i++)
        if(dis[i]<=d&&f[i]<=d) ans++;

    printf("%d\n",ans);

    return 0;
}