题目大意:
给你一棵树,树上有个特殊点,问有多少点到所有特殊点的距离小于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; }