题目链接：https://codeforces.com/problemset/problem/337/D
以下转自：https://www.cnblogs.com/Khada-Jhin/p/10195287.html
DP求直径的方法是对于每个点记录这个点子树中的最长链及与最长链处于不同子树中的次长链，用每个点的最长链+次长链更新直径，然后再将最长链上传到父节点更新父节点的最长链或次长链。这种求法适用于所有求树的直径的情况。
1、直径两端点一定是两个叶子节点
2、距离任意点最远的点一定是直径的一个端点，这个基于贪心求直径方法的正确性可以得出
3、对于两棵树，如果第一棵树直径两端点为(u,v)(u,v)，第二棵树直径两端点为(x,y)(x,y)，用一条边将两棵树连接，那么新树的直径一定是u,v,x,y,u,v,x,y,中的两个点
证明：如果新树直径不是原来两棵树中一棵的直径，那么新直径一定经过两棵树的连接边，新直径在原来每棵树中的部分一定是距离连接点最远的点，即一定是原树直径的一个端点。
4、对于一棵树，如果在一个点的上接一个叶子节点，那么最多会改变直径的一个端点
证明：假设在xx下面接一个点yy，直径变成了(u,x)(u,x),原树直径为(a,b)(a,b)，那么dis(u,x)>dis(a,b),dis(u,x)=dis(u,y)+1dis(u,x)>dis(a,b),dis(u,x)=dis(u,y)+1，即dis(u,y)+1>dis(a,b)dis(u,y)+1>dis(a,b)，如果dis(u,y)<dis(a,b)dis(u,y)<dis(a,b)，那么显然不成立；如果dis(u,y)=dis(a,b)dis(u,y)=dis(a,b)，那么(u,y)(u,y)也是原树的直径，符合上述结论。
5、若一棵树存在多条直径，那么这些直径交于一点且交点是这些直径的中点
#include <cstdio> #include <cstdlib> #include <cassert> #include <cstring> #include <bitset> #include <cmath> #include <cctype> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef vector<long long> VI; typedef unsigned long long ull; const ll inff = 0x3f3f3f3f3f3f3f3f; #define FOR(i,a,b) for(int i(a);i<=(b);++i) #define FOL(i,a,b) for(int i(a);i>=(b);--i) #define SZ(x) ((long long)(x).size()) #define REW(a,b) memset(a,b,sizeof(a)) #define inf int(0x3f3f3f3f) #define si(a) scanf("%d",&a) #define sl(a) scanf("%lld",&a) #define sd(a) scanf("%lf",&a) #define ss(a) scanf("%s",a) #define mod ll(1e9+7) #define pb push_back #define eps 1e-6 #define lc d<<1 #define rc d<<1|1 #define Pll pair<ll,ll> #define P pair<int,int> #define pi acos(-1) int n,m,dd,a[100008],x,y,pos,sd,sf,b[100008],ans; vector<int>g[100008]; void dfs(int u,int fa,int d,int z) { if(z&&d<=dd) b[u]++; if(a[u]&&d>sd) sd=d,pos=u; for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(v==fa) continue; dfs(v,u,d+1,z); } } void dfs1(int u,int fa,int d) { if(a[u]&&d>sd) sd=d,sf=u; for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(v==fa) continue; dfs1(v,u,d+1); } } int main() { cin.tie(0); cout.tie(0); cin>>n>>m>>dd; FOR(i,1,m) si(x),a[x]=1; FOR(i,1,n-1) { si(x),si(y); g[x].pb(y); g[y].pb(x); } dfs(1,0,0,0);sf=pos,sd=0,dfs1(pos,0,0); dfs(pos,0,0,1),dfs(sf,0,0,1); FOR(i,1,n) if(b[i]>=2) ans++; cout<<ans<<endl; return 0; }
