Submission #11379450
Source Code Expand
#include "bits/stdc++.h" using namespace std; typedef long long ll; const int INF = (1<<30); const ll INFLL = (1ll<<60); const ll MOD = (ll)(1e9+7); #define l_ength size void mul_mod(ll& a, ll b){ a *= b; a %= MOD; } void add_mod(ll& a, ll b){ a = (a<MOD)?a:(a-MOD); b = (b<MOD)?b:(b-MOD); a += b; a = (a<MOD)?a:(a-MOD); } int t,x=0,y=1; ll dp[1234][55][2],sp[2][5][55]; vector<int> g[1234]; void solve(int v, int p = -1){ int u,i,j,k,l; for(i=(g[v].l_ength()-1); i>=0; --i){ u = g[v][i]; if(u == p){ continue; } solve(u,v); } for(j=0; j<=2; ++j){ for(k=0; k<=t; ++k){ sp[x][j][k] = 0ll; } } sp[x][0][0] = 1ll; for(i=(g[v].l_ength()-1); i>=0; --i){ u = g[v][i]; if(u == p){ continue; } for(j=0; j<=2; ++j){ for(k=0; k<=t; ++k){ for(l=0; l<=t; ++l){ if(k+l>t){ break; } add_mod(sp[y][j][k+l],sp[x][j][k]*dp[u][l][0]%MOD); add_mod(sp[y][j+1][k+l],sp[x][j][k]*dp[u][l][1]%MOD); } } } for(j=0; j<=2; ++j){ for(k=0; k<=t; ++k){ sp[x][j][k] = 0ll; } } swap(x,y); } for(k=0; k<=t; ++k){ add_mod(dp[v][k][0],sp[x][0][k]); add_mod(dp[v][k+1][1],sp[x][0][k]); add_mod(dp[v][k][0],sp[x][1][k]); add_mod(dp[v][k][1],sp[x][1][k]); if(k){ add_mod(dp[v][k-1][0],sp[x][2][k]); } } } int main(void){ int n,i,a,b; cin >> n >> t; ++t; for(i=1; i<n; ++i){ cin >> a >> b; --a; --b; g[a].push_back(b); g[b].push_back(a); } solve(0); --t; cout << dp[0][t][0] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | P - うなぎ |
User | ransewhale |
Language | C++14 (GCC 5.4.1) |
Score | 6 |
Code Size | 1584 Byte |
Status | AC |
Exec Time | 31 ms |
Memory | 1280 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 | 31 ms | 1280 KB |
01 | AC | 2 ms | 1152 KB |
02 | AC | 31 ms | 1152 KB |
03 | AC | 31 ms | 1152 KB |
04 | AC | 31 ms | 1152 KB |
05 | AC | 31 ms | 1152 KB |
06 | AC | 31 ms | 1152 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |