Submission #6443330


Source Code Expand

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll dp[1000][51][3];
ll sdp[1001][51][3];
vector<ll> G[1000];
int N, K;
void solve(int v, int p) {
	vector<int> child;
	for (int to : G[v]) {
		if (to == p) continue;
		child.push_back(to);
		solve(to, v);
	}
	memset(sdp, 0, sizeof(sdp));
	sdp[0][0][0] = 1;
	for (int i = 0; i < child.size(); i++) {
		for (int j = 0; j <= K; j++) {
			for (int k = 0; k <= K; k++) {
				if (j + k <= K) {
					ll sum = 0;
					for (int d = 0; d < 3; d++) (sum += dp[child[i]][k][d]) %= MOD;
					for (int d = 0; d < 3; d++) (sdp[i + 1][j + k][d] += sdp[i][j][d] * sum%MOD) %= MOD;
					(sdp[i + 1][j + k][1] += sdp[i][j][0] * dp[child[i]][k][1] % MOD) %= MOD;
					(sdp[i + 1][j + k][2] += sdp[i][j][1] * dp[child[i]][k][0] % MOD) %= MOD;
				}
				if (j + k + 1 <= K) {
					(sdp[i + 1][j + k + 1][1] += sdp[i][j][0] * dp[child[i]][k][0] % MOD) %= MOD;
				}
				if (0 <= j + k - 1 && j + k - 1 <= K) {
					(sdp[i + 1][j + k - 1][2] += sdp[i][j][1] * dp[child[i]][k][1] % MOD) %= MOD;
				}
			}
		}
	}
	for (int i = 0; i <= K; i++) for (int j = 0; j < 3; j++) dp[v][i][j] = sdp[child.size()][i][j];
}
 int main() {
	 cin >> N >> K;
	 for (int i = 0; i + 1 < N; i++) {
		 int a, b;
		 cin >> a >> b; a--; b--;
		 G[a].push_back(b);
		 G[b].push_back(a);
	 }
	 solve(0, -1);
	 ll ans = 0;
	 for (int i = 0; i < 3; i++) (ans += dp[0][K][i]) %= MOD;
	 cout << ans << endl;
}

Submission Info

Submission Time
Task P - うなぎ
User Div9851
Language C++14 (GCC 5.4.1)
Score 6
Code Size 1500 Byte
Status AC
Exec Time 119 ms
Memory 2944 KB

Judge Result

Set Name All
Score / Max Score 6 / 6
Status
AC × 9
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 90, 91
Case Name Status Exec Time Memory
00 AC 119 ms 2944 KB
01 AC 61 ms 2688 KB
02 AC 119 ms 2688 KB
03 AC 119 ms 2688 KB
04 AC 119 ms 2688 KB
05 AC 119 ms 2688 KB
06 AC 119 ms 2688 KB
90 AC 2 ms 1408 KB
91 AC 2 ms 1408 KB