Give you a tree. There are some important points on the tree. Let you choose a point set that only contains important points. The farthest two points in the point set are not more than k. how many choices are there

After thinking for a long time, the explanation is too brief...

dp[i][j] represents the number of schemes with the farthest distance k from point I in this subtree.

Considering how to transfer from the subtree, obviously when we traverse to a new subtree, we need to multiply all previous schemes by the scheme of this subtree to update.

That is DP [u] [max (I, j + 1] + = dp[u][i]*dp[to][j]

The complexity of violence update is k^2. It needs to be prefixed and maintained,

Finally, if this point is optional, you can choose this point or not, multiply by 2, and then add this point only.

In the final calculation of the sum, if this point is not the root, only the case with the length of k will be added, because other cases may be updated, and it will be calculated in his ancestry, if not all schemes will be added.

#include <bits/stdc++.h>

using namespace std;
#define N 5010
#define ll long long
#define mod 1000000007
#define go(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define add(a,b) ((a+=(b))%=mod)
ll dp[N][N],sum[N][N],f[N],ans;
vector<int>path[N];
int is[N];
int n,m,k,x,y;
void cal(int u,int to){
    go(i,1,k-1)f[i]=dp[u][i]*sum[to][min(i,k-i)-1]%mod;
    go(i,1,k-1)add(f[i],sum[u][min(i,k-i)]*dp[to][i-1]%mod);
    go(i,1,k/2)add(f[i],(mod-dp[u][i]*dp[to][i-1]%mod)%mod);//Tolerance and exclusion, subtraction of repeated calculation
    go(i,1,k)
        add(dp[u][i],(dp[to][i-1]+f[i])%mod),//Plus the scheme of this subtree
        sum[u][i]=(sum[u][i-1]+dp[u][i])%mod;
}
void dfs(int u,int fa){
    for(auto to:path[u]){
        if(to==fa)continue;
        dfs(to,u);
        cal(u,to);
    }
    if(is[u]){//If this point is optional
        sum[u][0]=dp[u][0]=1;//Just choose this point
        go(i,1,k)
            add(dp[u][i],dp[u][i]),//Sorting it doesn't choose two kinds, so multiply by 2
            sum[u][i]=(sum[u][i-1]+dp[u][i])%mod;//Update prefix and
    }
    add(ans,u!=1?dp[u][k]:sum[u][k]);//If this point is root, add all cases, otherwise only add the case with length k
}
int main()
{

    n=m=k=5000;
    go(i,2,n)
        path[i].push_back(i-1),
        path[i-1].push_back(i);
    go(i,1,n)is[i]=1;
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}