Book of Evil CodeForces - 337D

​​http://codeforces.com/problemset/problem/337/D​​

給一棵樹 其中有m個點是重要點 一個點到這m給點的距離都小于等于d才算符合條件 問有多少點符合條件

把這m個點想象成m個半徑為d的圓 題目就是問有多少點被這m個半徑相同的圓全部覆寫 可以想到要求m個點中相距最遠的兩個點 具體怎麼求其實就是樹的直徑的變形了

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

struct node
{
    int v;
    int next;
};

node edge[2*maxn];
int first[maxn],p[maxn],dis1[maxn],dis2[maxn];
int n,m,d,num,p1,p2;

void addedge(int u,int v)
{
    edge[num].v=v;
    edge[num].next=first[u];
    first[u]=num++;
}

void dfs(int *dis,int cur,int fa)
{
    int i,v;
    for(i=first[cur];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v!=fa)
        {
            dis[v]=dis[cur]+1;
            dfs(dis,v,cur);
        }
    }
}

int main()
{
    int i,u,v,maxx,ans;
    scanf("%d%d%d",&n,&m,&d);
    for(i=1;i<=m;i++) scanf("%d",&p[i]);
    memset(first,-1,sizeof(first));
    num=0;
    for(i=1;i<=n-1;i++)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    dis1[p[1]]=0;
    dfs(dis1,p[1],0);
    maxx=-1;
    for(i=1;i<=m;i++) if(maxx<dis1[p[i]]) maxx=dis1[p[i]],p1=p[i];
    dis1[p1]=0;
    dfs(dis1,p1,0);
    maxx=-1;
    for(i=1;i<=m;i++) if(maxx<dis1[p[i]]) maxx=dis1[p[i]],p2=p[i];
    dis2[p2]=0;
    dfs(dis2,p2,0);
    /*
    printf("*%d %d*\n",p1,p2);
    for(i=1;i<=n;i++) printf("%d ",dis1[i]);
    printf("\n");
    for(i=1;i<=n;i++) printf("%d ",dis2[i]);
    printf("\n");
    */
    ans=0;
    for(i=1;i<=n;i++)
    {
        if(dis1[i]<=d&&dis2[i]<=d) ans++;
    }
    printf("%d\n",ans);
    return 0;
}