結果
問題 | No.1488 Max Score of the Tree |
ユーザー |
![]() |
提出日時 | 2021-04-23 21:46:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 689 bytes |
コンパイル時間 | 152 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 63,660 KB |
最終ジャッジ日時 | 2024-07-04 07:52:01 |
合計ジャッジ時間 | 3,099 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
n,K = map(int,input().split()) g = [[] for _ in range(n)] for _ in range(n-1): a,b,c = map(int,input().split()) g[a-1].append((b-1,c)) g[b-1].append((a-1,c)) ans = 0 order = [] wt = [0]*n st = [0] parent = [-1]*n while st: v = st.pop() order.append(v) for c,d in g[v]: if c != parent[v]: st.append(c) parent[c] = v wt[c] = d res = [] size = [0]*n for v in order[1:][::-1]: if len(g[v])==1: size[v] = 1 ans += size[v]*wt[v] res.append((size[v],wt[v])) size[parent[v]] += size[v] dp = [0]*(K+1) for v,w in res: for i in range(w,K+1)[::-1]: dp[i] = max(dp[i], dp[i-w] + v*w) print(ans+max(dp))