結果
問題 |
No.1488 Max Score of the Tree
|
ユーザー |
|
提出日時 | 2022-01-27 20:53:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 98 ms / 2,000 ms |
コード長 | 731 bytes |
コンパイル時間 | 425 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 61,568 KB |
最終ジャッジ日時 | 2024-12-26 02:17:40 |
合計ジャッジ時間 | 3,513 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
n, k = map(int, input().split()) edges = [[] for _ in range(n)] for _ in range(n - 1): a, b, c = map(int, input().split()) a -= 1 b -= 1 edges[a].append((b, c)) edges[b].append((a, c)) wv = [] ans = 0 def dfs(pos, bpos, cc): if len(edges[pos]) == 1: ret = 1 if pos != 0: global ans ans += cc else: ret = 0 for npos, c in edges[pos]: if npos == bpos: continue tmp = dfs(npos, pos, cc + c) wv.append((c, c * tmp)) ret += tmp return ret dfs(0, -1, 0) dp = [0] * (k + 1) for w, v in wv: for i in range(k, w - 1, -1): dp[i] = max(dp[i], dp[i - w] + v) print(dp[-1] + ans)