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 |
|
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 |