結果
問題 |
No.1488 Max Score of the Tree
|
ユーザー |
|
提出日時 | 2022-07-30 08:47:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 177 ms / 2,000 ms |
コード長 | 1,016 bytes |
コンパイル時間 | 252 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 142,208 KB |
最終ジャッジ日時 | 2024-07-20 04:05:43 |
合計ジャッジ時間 | 4,585 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import sys from collections import deque input = sys.stdin.buffer.readline N, K = map(int, input().split()) edges = [] T = [[] for _ in range(N)] for _ in range(N - 1): a, b, c = map(int, input().split()) a -= 1 b -= 1 edges.append((a, b, c)) T[a].append((b, c)) T[b].append((a, c)) dist = [None] * N dist[0] = 0 d = deque([0]) dfs_order = [] is_leaf = [True] * N while d: v = d.pop() dv = dist[v] for x, c in T[v]: if dist[x] is None: dfs_order.append((v, x)) dist[x] = dv + c d.append(x) is_leaf[v] = False desc_leaves = [int(l) for l in is_leaf] for v, x in reversed(dfs_order): desc_leaves[v] += desc_leaves[x] dp = [-10 ** 9] * (K + 1) dp[0] = 0 for a, b, c in edges: new_dp = dp.copy() value = c * (min(desc_leaves[a], desc_leaves[b])) for i in range(K + 1 - c): new_dp[i + c] = max(new_dp[i + c], dp[i] + value) dp = new_dp print(max(dp) + sum(ds * l for ds, l in zip(dist, is_leaf)))