Book of Evil

题意

你有一棵有个节点树，其中有个已告知的标记点，求个点中，有多少个点到这个标记点的最大距离不大于。

分析

。所以我们可以处理一下，跑两次，分别把子树内和子树外两种情况处理出来，最后统计答案时，两者同时满足就可以纳入。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e5+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,m,d,cnt,py,ans,u,v;
int head[N],dis[N][2],gw[N];
struct node
{
    int nxt,to;
}e[N<<1];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

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

void dfs(int u,int fa,int dep,int f)
{
    dis[u][f]=dep;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v!=fa)dfs(v,u,dep+1,f);
    }
}

int main()
{
    n=read(),m=read(),d=read();
    for(int i=1;i<=m;i++)
        gw[i]=read();
    for(int i=1;i<n;i++)
    {
        u=read(),v=read();
        add(u,v);add(v,u);
    }
    dfs(1,0,0,1);
    for(int i=1;i<=m;i++)
     if(dis[gw[i]][1]>dis[py][1]) 
        py=gw[i];
    dfs(py,0,0,1);
    py=0;
    for(int i=1;i<=m;i++)
     if(dis[gw[i]][1]>dis[py][1]) 
        py=gw[i];
    dfs(py,0,0,2);
    for(int i=1;i<=n;i++) if(dis[i][1]<=d&&dis[i][2]<=d) ans++;
    printf("%d", ans);
    return 0;
}