結果
問題 | No.196 典型DP (1) |
ユーザー | heno239 |
提出日時 | 2019-02-26 11:45:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 859 bytes |
コンパイル時間 | 1,637 ms |
コンパイル使用メモリ | 174,768 KB |
実行使用メモリ | 20,608 KB |
最終ジャッジ日時 | 2024-06-12 00:16:43 |
合計ジャッジ時間 | 3,153 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1000000007;#define rep(i,n) for(int i=0;i<n;i++)vector<int> G[2000];bool used[2000];int k;vector<ll> dp[2000];void merge(int i,int j){int l1=dp[i].size();int l2=dp[j].size();vector<ll> nex;nex.resize(l1+l2-1,0);rep(i1,l1){rep(i2,l2){nex[i1+i2]+=dp[i][i1]*dp[j][i2]%mod;nex[i1+i2]%=mod;}}dp[i]=nex;}void dfs(int id){used[id]=true;dp[id].resize(2,0);ll sum=1;dp[id][0]=1;rep(j,G[id].size()){int to=G[id][j];if(used[to])continue;dfs(to);merge(id,to);int len=dp[to].size();sum=sum*dp[to][len-1]%mod;}int len=dp[id].size();dp[id][len-1]+=sum;dp[id][len-1]%=mod;}int main(){int n;cin>>n>>k;rep(i,n-1){int a,b;cin>>a>>b;G[a].push_back(b);G[b].push_back(a);}dfs(0);cout<<dp[0][k]<<endl;}