結果
問題 | No.196 典型DP (1) |
ユーザー | tenten |
提出日時 | 2021-05-20 09:59:54 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,175 bytes |
コンパイル時間 | 2,393 ms |
コンパイル使用メモリ | 79,524 KB |
実行使用メモリ | 216,200 KB |
最終ジャッジ日時 | 2024-10-10 07:11:48 |
合計ジャッジ時間 | 42,660 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 TLE * 6 |
ソースコード
import java.io.*;import java.util.*;public class Main {static ArrayList<TreeMap<Integer, Long>> dp = new ArrayList<>();static final int MOD = 1000000007;static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();public static void main(String[] args) throws Exception {Scanner sc = new Scanner();int n = sc.nextInt();int k = sc.nextInt();for (int i = 0; i < n; i++) {dp.add(new TreeMap<>());dp.get(i).put(0, 1L);graph.add(new ArrayList<>());}for (int i = 0; i < n - 1; i++) {int a = sc.nextInt();int b = sc.nextInt();graph.get(a).add(b);graph.get(b).add(a);}getChildren(0, 0);System.out.println(dp.get(0).getOrDefault(k, 0L));}static int getChildren(int idx, int parent) {int count = 1;for (int x : graph.get(idx)) {if (x == parent) {continue;}count += getChildren(x, idx);Integer key = Integer.MAX_VALUE;while ((key = dp.get(idx).lowerKey(key)) != null) {long org = dp.get(idx).get(key);for (int y : dp.get(x).keySet()) {if (y == 0) {continue;}dp.get(idx).put(key + y, (dp.get(idx).getOrDefault(key + y, 0L) + org * dp.get(x).get(y) % MOD) % MOD);}}}dp.get(idx).put(count, 1L);return count;}}class Scanner {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer("");public Scanner() throws Exception {}public int nextInt() throws Exception {return Integer.parseInt(next());}public long nextLong() throws Exception {return Long.parseLong(next());}public String next() throws Exception {if (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}return st.nextToken();}}