CodeForces 735E Ostap and Tree

Description

Ostap already settled down in Rio de Janiero suburb and started to grow a tree in his garden. Recall that a tree is a connected undirected acyclic graph.

Ostap's tree now has n vertices. He wants to paint some vertices of the tree black such that from any vertex u there is at least one black vertex v at distance no more than k. Distance

As this number of ways to paint the tree can be large, Ostap wants you to compute it modulo 109 + 7. Two ways to paint the tree are considered different if there exists a vertex that is painted black in one way and is not painted in the other one.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ min(20, n - 1)) — the number of vertices in Ostap's tree and the maximum allowed distance to the nearest black vertex. Don't miss the unusual constraint for k.

Each of the next n - 1 lines contain two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of vertices, connected by the i-th edge. It's guaranteed that given graph is a tree.

Output

Print one integer — the remainder of division of the number of ways to paint the tree by 1 000 000 007 (109 + 7).

Sample Input

Input

2 0

1 2

Output

1

Input

2 1

1 2

Output

3

Input

4 1

1 2

2 3

3 4

Output

9

Input

7 2
1 2
2 3
1 4
4 5
1 6
6 7      

Output

91

十分有趣的树形dp（看人家代码学会的T_T），设dp[x][i]表示距离x所在的子树中，

距离x最近的黑点距离为i的合法方案数。

递推dp[x][i]，用y来表示x的某个子节点，显然，在递推x的时候，y已经知道答案了。

现在考虑dp[x][i]的结果，从dp[y][j]来计算。

如果i+(j+1)<=2*m的情况，显然我们取较小的距离f[min(i,j+1)]+=dp[x][i]*dp[y][j]是合法的答案。

对于i+j+1>2*m的情况，显然是不合法的，因为中间有的点不能被黑色点覆盖，

所以我们要保留最远的那个，作为下次可能合法的答案来统计。

f[max(i,j+1)]+=dp[x][i]*dp[y][j]，这样统计过一次后，把f数组重新覆盖给dp[x][i]就是新的结果。

初始化的时候，dp[x][0]=1,显然该点是可以涂成黑色的，然后是dp[x][k+1]=1，

因为这样第一次统计的时候，可以减少特判的部分。

最后∑dp[1][0..k]就是答案了。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])
#define inone(x) scanf("%d",&x)
#define intwo(x,y) scanf("%d%d",&x,&y)
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int n, m, x, y;
int ft[N], nt[N], u[N], sz;
long long dp[N][N], f[N], ans;

void dfs(int x, int fa)
{
  dp[x][0] = dp[x][m + 1] = 1;
  loop(i, ft[x], nt)
  {
    if (u[i] == fa) continue;
    dfs(u[i], x);
    memset(f, 0, sizeof(f));
    for (int j = 0; j <= 2 * m + 1; j++)
    {
      for (int k = 0; k <= 2 * m; k++)
      {
        if (j + k <= 2 * m)
        {
          (f[min(j, k + 1)] += 1LL * dp[x][j] * dp[u[i]][k] % mod) %= mod;
        }
        else
        {
          (f[max(j, k + 1)] += 1LL * dp[x][j] * dp[u[i]][k] % mod) %= mod;
        }
      }
    }
    memcpy(dp[x], f, sizeof(f));
  }
}

int main()
{
  while (intwo(n, m) != EOF)
  {
    rep(i, 1, n) ft[i] = -1;
    memset(dp, sz = 0, sizeof(dp));
    rep(i, 1, n - 1)
    {
      intwo(x, y);
      u[sz] = y; nt[sz] = ft[x]; ft[x] = sz++;
      u[sz] = x; nt[sz] = ft[y]; ft[y] = sz++;
    }
    dfs(1, ans = 0);
    rep(i, 0, m) (ans += dp[1][i]) %= mod;
    printf("%lld\n", ans);
  } 
  return 0;
}