Book of Evil

                                        Book of Evil

Problem Link

#include <iostream>

#include <vector>

#include <cstring>

#include <stdio.h>

#define sf(i) scanf("%d", &i)

#define pf(i) printf("%d\n", i)

#define pb push_back

using namespace std;

const int N = 1e5 + 1;

int h[N];

bool mark[N],ans[N];

vector<int> g[N];

int n, m, d, D, R;

void dfs(int s, int p)

{

    h[s] = h[p] + 1;

    ans[s] &= (h[s] <= d);

    if(mark[s] && h[s] > D)

    {

        D = h[s], R = s;

    }

    for(int i = 0; i < g[s].size(); i++)

    {

        int v = g[s][i];

        if(v == p)

            continue;

        dfs(v,s);

    }

}

int main()

{

    sf(n), sf(m), sf(d);

    int a, b;

    D = 0;

    h[0] = -1;

    for(int i = 1; i <= m; i++)

    {

        sf(R);

        mark[R] = true;

    }

    for(int i = 1; i <= n - 1; i++)

    {

        sf(a), sf(b);

        g[a].pb(b);

        g[b].pb(a);

    }

    memset(ans, true, sizeof(ans));

    /* calculate the distance of other vertex from this node and finds the marked node farthest from this marked node */

    dfs(R, 0);

    /* calculate the distance of other vertex from this node and find the farthest marked node from this node */

    dfs(R, 0);

    /* calculate the distance of other vertex from this node */

    dfs(R, 0);

    /*if a node is at most d distance apart from two farthest marked node then that node should be added in the answer */

    int res = 0;

    for(int i = 1; i <= n; i++)

    {

        if(ans[i])

            res++;

    }

    pf(res);

    return 0;

}