結果
問題 | No.1488 Max Score of the Tree |
ユーザー | sgsw |
提出日時 | 2021-04-30 02:33:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,204 ms / 2,000 ms |
コード長 | 1,775 bytes |
コンパイル時間 | 355 ms |
コンパイル使用メモリ | 87,224 KB |
実行使用メモリ | 270,604 KB |
最終ジャッジ日時 | 2023-09-25 02:29:27 |
合計ジャッジ時間 | 17,449 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 882 ms
228,020 KB |
testcase_01 | AC | 906 ms
229,396 KB |
testcase_02 | AC | 948 ms
237,748 KB |
testcase_03 | AC | 937 ms
237,320 KB |
testcase_04 | AC | 916 ms
219,044 KB |
testcase_05 | AC | 72 ms
71,224 KB |
testcase_06 | AC | 312 ms
134,952 KB |
testcase_07 | AC | 606 ms
187,168 KB |
testcase_08 | AC | 400 ms
147,292 KB |
testcase_09 | AC | 350 ms
130,788 KB |
testcase_10 | AC | 600 ms
191,888 KB |
testcase_11 | AC | 1,204 ms
270,604 KB |
testcase_12 | AC | 89 ms
76,808 KB |
testcase_13 | AC | 227 ms
101,036 KB |
testcase_14 | AC | 500 ms
157,956 KB |
testcase_15 | AC | 357 ms
132,448 KB |
testcase_16 | AC | 127 ms
87,000 KB |
testcase_17 | AC | 283 ms
131,876 KB |
testcase_18 | AC | 643 ms
179,432 KB |
testcase_19 | AC | 436 ms
163,116 KB |
testcase_20 | AC | 225 ms
103,816 KB |
testcase_21 | AC | 158 ms
99,576 KB |
testcase_22 | AC | 333 ms
121,252 KB |
testcase_23 | AC | 69 ms
71,148 KB |
testcase_24 | AC | 69 ms
71,252 KB |
testcase_25 | AC | 70 ms
71,212 KB |
testcase_26 | AC | 304 ms
138,236 KB |
testcase_27 | AC | 121 ms
83,660 KB |
testcase_28 | AC | 185 ms
95,484 KB |
testcase_29 | AC | 228 ms
106,652 KB |
testcase_30 | AC | 762 ms
209,968 KB |
testcase_31 | AC | 1,150 ms
269,980 KB |
ソースコード
import sys def input(): return sys.stdin.readline().rstrip() """ Do not get stuck on a problem for more than 20 minutes Just check the editorial :) There should be something else to do insead """ INF = 1 << 128 def slv(): n, k = map(int, input().split()) g = [[]for i in range(n)] edge = [] for i in range(n - 1): u, v, c = map(int, input().split()) u -= 1 v -= 1 g[u].append((v,c)) g[v].append((u,c)) edge.append((u, v, c)) visited = [INF]*(n) cnt = [0]*(n) par = [-1]*(n) ans = 0 def dfs(S): if visited[S] == INF: visited[S] = 0 for adj,c in g[S]: if visited[adj] == INF: par[adj] = S visited[adj] = visited[S] + c dfs(adj) if all(visited[u] < visited[S] for u,c in g[S]): cnt[S] = 1 if par[S] >= 0: cnt[par[S]] += cnt[S] dfs(0) for i in range(n): if all(visited[u] < visited[i] for u,c in g[i]): ans += visited[i] data = [] for u, v, c in edge: if visited[u] < visited[v]: data.append((cnt[v], c)) else: data.append((cnt[u], c)) dp = [[-INF]*(k + 1) for i in range(n)] dp[0][0] = 0 for i in range(1,n): cnt,cost = data[i - 1] V,cost = cnt * cost,cost for j in range(k + 1): if j + cost <= k: dp[i][j + cost] = max(dp[i][j + cost],dp[i - 1][j] + V) dp[i][j] = max(dp[i][j],dp[i - 1][j]) ans += max(dp[n - 1][c] for c in range(k + 1)) print(ans) return def main(): t = 1 for i in range(t): slv() return if __name__ == "__main__": main()