結果
問題 | No.1488 Max Score of the Tree |
ユーザー |
|
提出日時 | 2021-04-23 21:46:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 369 ms / 2,000 ms |
コード長 | 1,220 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 142,976 KB |
最終ジャッジ日時 | 2024-07-04 07:51:53 |
合計ジャッジ時間 | 7,030 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
N, K = map(int, input().split()) adj = [[] for i in range(N)] E = [] for i in range(N - 1): a, b, c = map(int, input().split()) a -= 1 b -= 1 adj[a].append((b, c)) adj[b].append((a, c)) E.append((a, b, c)) depth = [-1] * N depth[0] = 0 from collections import deque qu = deque([0]) while len(qu): v = qu.popleft() for nv, c in adj[v]: if depth[nv] == -1: depth[nv] = depth[v] + c qu.append(nv) dp = [1] * N for v in range(N): for nv, c in adj[v]: if depth[nv] > depth[v]: dp[v] = 0 break ans = sum([dp[i] * depth[i] for i in range(N)]) node = [i for i in range(N)] node.sort(key = lambda x: depth[x], reverse = True) for v in node: for nv, c in adj[v]: if depth[nv] < depth[v]: continue dp[v] += dp[nv] V = [] for i in range(N - 1): a, b, c = E[i] if depth[a] > depth[b]: a, b = b, a #aが浅い V.append(c * dp[b]) dp = [[0] * (K + 1) for i in range(N)] for i in range(N - 1): for j in range(K + 1): dp[i + 1][j] = dp[i][j] if j + E[i][2] <= K: dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + E[i][2]] + V[i]) print(max(dp[-1]) + ans)