提出 #41139446

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int N, K;
vector<vector<int>> edges;

// dp[i][j][k] : 部分木 i において、j 本のパスを選ぶ選び方のうち、頂点 i の次数が k であるものの個数
mint dp[1005][55][3];

void dfs(int x, int par)
{
  vector<int> child;
  for (int i : edges[x]){
    if (i != par){
      child.push_back(i);
      dfs(i, x);
    }
  }

  int nchild = (int) child.size();

  // dp2[x][y][z] :  x 個の子までみたとき、y 本のパスを選ぶ選び方のうち、頂点 i へのパスの本数が z
  vector<vector<vector<mint>>> dp2(nchild + 1,
				   vector<vector<mint>>(K + 1,
							vector<mint>(3)));

  dp2[0][0][0] = 1;

  for (int i = 0; i < nchild; i++){
    int l = child[i];
    for (int j = 0; j <= K; j++){
      for (int k = 0; k <= 2; k++){
	for (int m = 0; m <= K; m++){ // ループ条件を m + j <= K としたくなるが我慢
	  for (int n = 0; n <= 2; n++){
	    // (A) x - l の辺はつながない場合
	    if (j + m <= K){
	      dp2[i+1][j+m][k] += dp2[i][j][k] * dp[l][m][n];
	    }

	    // (B) x - l をつなぐ場合は、(k, n) の組み合わせで４通り
	    // (B-1) (k, n) = (1, 1)
	    //       2 つのパスが点 x でつながる
	    if (k == 1 && n == 1 && j + m - 1 >= 0 && j + m - 1 <= K){
	      dp2[i+1][j+m-1][2] += dp2[i][j][k] * dp[l][m][n];
	    }

	    // (B-2) (k, n) = (1, 0)
	    //       k 側のパスのうち１つが伸びる
	    if (k == 1 && n == 0 && j+m <= K){
	      dp2[i+1][j+m][k+1] += dp2[i][j][k] * dp[l][m][n];
	    }
	    
	    // (B-3) (k, n) = (0, 1)
	    //       n 側のパスのうち１つが伸びる
	    if (k == 0 && n == 1 && j + m <= K){
	      dp2[i+1][j+m][1] += dp2[i][j][k] * dp[l][m][n];
	    }

	    // (B-4) (k, n) = (0, 0)
	    //       x - l  が孤立パスになる
	    if (k == 0 && n == 0 && j + m + 1 <= K){
	      dp2[i+1][j+m+1][1] += dp2[i][j][k] * dp[l][m][n];
	    }
	  }
	}
      }
    }
  }

  for (int i = 0; i <= K; i++){
    for (int j = 0; j <= 2; j++){
      dp[x][i][j] = dp2[nchild][i][j];
    }
  }
}

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  cin >> N >> K;
  edges.resize(N);

  for (int i = 0; i < N - 1; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  dfs(0, -1);

  mint ans = 0;
  for (int i = 0; i <= 2; i++){
    ans += dp[0][K][i];
  }

  cout << ans.val() << endl;
  return 0;
}

提出情報

ジャッジ結果