题目
n(n<=5e3)个点的树，树上有m(m<=5e3)个重要的点，
你需要选定一个重要的点的非空集合，使得集合内任意两个点的距离不超过k(k<=5e3)，
求选点的方案数，答案对1e9+7取模
思路来源
https://blog.csdn.net/cat_pikapikapi/article/details/90521780
题解
dp[i][j]表示在i的子树里，最远点距离i的距离为j时，选点集合满足两两不超过k的方案数
u是v的父亲，考虑v怎么往u这棵树上挂，两棵树合并的时候统计方案，
类似背包，记u的选点深度为p，v的选点深度为q，新方案仍然合法的条件是p+q+1<=k，
此外，还有只在v处选点的情形，也要转移到u这棵树里，
由于此时u为根没有选点，故可以突破q+1<=k的限制，
但是，若u为根，则dp[u][0]为1，此时，深度为p的方案数加上选u的方案数时，
只能考虑深度p<=k的情形，因为此时根必取了
最后的根1是统计了该树内所有子树的答案，但可能由于1附近都没取点，
导致很远的距离选点满足<=k的方案数，被转移上来时，已经>k了，
但是>k的部分没取点，这样也是合法的，故统计答案时统计到dep[1]
复杂度看似O(n^3)，限制深度了之后，可能就近似O(n^2)了吧
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define pb push_back
const int N=5e3+10,mod=1e9+7;
int n,m,k,u,v,dep[N];
int dp[N][N],now[N];//dp[i][j]表示以i为根的子树 最远关键点为j的方案数
vector<int>e[N];
bool ok[N];
void dfs(int u,int fa){
dep[u]=0;
for(int i=0;i<e[u].size();++i){
int v=e[u][i];
if(v==fa)continue;
dfs(v,u);
dep[u]=max(dep[u],dep[v]+1);
for(int p=0;p<=dep[u];++p){
now[p]=dp[u][p];
}
for(int p=0;p<=dep[u] && p<=k;++p){
for(int q=0;q<=dep[v] && p+q+1<=k;++q){
(now[max(p,q+1)]+=1ll*dp[u][p]*dp[v][q]%mod)%=mod;//把轻儿子往重儿子树上挂的方案数 取之前的一些子树 必取当前子树
}
}
for(int q=0;q<=dep[v];++q){//此时不取根u 只考虑v子树距离+1的情形 所以最后统计答案时要到[0,dep[1]]里统计
(now[q+1]+=dp[v][q])%=mod;
}
for(int p=0;p<=dep[u];++p){
dp[u][p]=now[p];
}
}
if(ok[u]){
dp[u][0]=1;
for(int p=1;p<=dep[u] && p<=k;++p){
dp[u][p]=(dp[u][p]+dp[u][p])%mod;//原来都是不取根的方案 现在加上距离k以内的 取根的方案
}
}
for(int p=0;p<=dep[u];++p){
}
}
int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
memset(dp,0,sizeof dp);
memset(now,0,sizeof now);
for(int i=1;i<=n;++i){
ok[i]=0;
e[i].clear();
}
for(int i=1;i<n;++i){
scanf("%d%d",&u,&v);
e[u].pb(v);e[v].pb(u);
}
for(int i=1;i<=m;++i){
scanf("%d",&v);
ok[v]=1;
}
dfs(1,-1);
int ans=0;
for(int i=0;i<=dep[1];++i){
ans=(ans+dp[1][i])%mod;
}
printf("%d\n",ans);
}
return 0;
}
