图片说明
图片说明
题目大意:
给你一棵树,树上有个特殊点,问有多少点到所有特殊点的距离小于d.
思路:
又是学习大佬题解的一天我好菜啊
先对特殊点求一个树的直径,然后枚举所有点,如果它到直径两端的距离小于等于d,说明这些点满足题目要求。
求特殊点的直径,三次DFS即可,先从根求一波最长的特殊点,然后从特殊的再求一波最长的另外一个特殊端点,最优另外一个特殊端点再求一下到各个点的距离,然后枚举一下就行了。
这题一开始写了一个暴力,然后写树dp,苦于一个点到特殊点的最大距离不会求。。。。太菜了我。。还是这个做法香(逃)
代码:

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

const int maxn = 2e5 + 10;
vector<int>G[maxn];
int n,m,d;
int p[maxn];
int dis1[maxn],dis2[maxn],dis3[maxn];
void dfs1(int u,int fu,int dep){
    dis1[u] = dep;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fu){
            dfs1(v,u,dep + 1);
        }
    }
}
void dfs2(int u,int fu,int dep){
    dis2[u] = dep;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fu){
            dfs2(v,u,dep + 1);
        }
    }
}
void dfs3(int u,int fu,int dep){
    dis3[u] = dep;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fu){
            dfs3(v,u,dep + 1);
        }
    }
}
void solved(){
    scanf("%d%d%d",&n,&m,&d);
    for(int i = 1; i <= m; i++){
        cin>>p[i];
    }
    for(int i = 1; i <= n - 1; i ++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1,0,0);    
    int L = 0;
    for(int i = 1; i <= m; i++)
        if(dis1[p[i]] > dis1[L])
            L = p[i];
    dfs2(L,0,0);
    int R = 0;
    for(int i = 1; i <= m; i++)
        if(dis2[p[i]] > dis2[R])
            R = p[i];
    dfs3(R,0,0);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(dis2[i] <= d && dis3[i] <= d)ans++;
    }
    cout<<ans<<endl;
}
int main(){
    solved();
    return 0;
}