結果

問題 No.196 典型DP (1)
コンテスト
ユーザー ei1333333
提出日時 2015-09-09 15:26:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 822 bytes
コンパイル時間 1,295 ms
コンパイル使用メモリ 160,356 KB
実行使用メモリ 17,536 KB
最終ジャッジ日時 2024-07-19 05:04:07
合計ジャッジ時間 2,559 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

int N, K;
vector< int > graph[2000];

int dp[2000][2001];
int num[2000];
int rec(int idx, int prev)
{
  for(int i = 0; i < graph[idx].size(); i++) {
    if(graph[idx][i] != prev) rec(graph[idx][i], idx);
  }
  dp[idx][0] = 1;
  num[idx] = 1;
  for(int i = 0; i < graph[idx].size(); i++) {
    if(graph[idx][i] == prev) continue;
    for(int j = num[idx]; j >= 0; j--) {
      for(int k = num[graph[idx][i]]; k >= 1; k--) {
        dp[idx][j + k] += dp[idx][j] * dp[graph[idx][i]][k];
      }
    }
    num[idx] += num[graph[idx][i]];
  }
  dp[idx][num[idx]] = 1;
  return(dp[idx][K]);
}

int main()
{
  cin >> N >> K;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  cout << rec(0, -1) << endl;
}
0