結果
問題 |
No.1488 Max Score of the Tree
|
ユーザー |
|
提出日時 | 2022-08-03 02:48:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 266 ms / 2,000 ms |
コード長 | 866 bytes |
コンパイル時間 | 233 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 148,012 KB |
最終ジャッジ日時 | 2024-07-23 20:52:48 |
合計ジャッジ時間 | 5,840 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
N,K = map(int,input().split()) lsg = [[] for i in range(N)] h = [] for i in range(N-1): a,b,c = map(int,input().split()) a -= 1 b -= 1 h.append((a,b,c)) lsg[a].append((b,c)) lsg[b].append((a,c)) dp = [0]*(N) def dfs(k,p): #node k につながっている葉の数。 if p >= 0 and len(lsg[k]) == 1: dp[k] = 1 return 1 ret = 0 for j,c in lsg[k]: if j == p: continue ret += dfs(j,k) dp[k] = ret return ret dfs(0,-1) scores = [] ans = 0 for i in range(N-1): a,b,c = h[i] g = min(dp[a],dp[b])*c scores.append((c,g)) ans += g dp2 = [0]*(K+1) for i in range(N-1): c,g = scores[i] dp3 = [0]*(K+1) for j in range(K+1): if j + c <= K: dp3[j+c] = max(dp2[j]+g,dp2[j+c]) dp3[j] = max(dp2[j],dp3[j]) dp2 = dp3 print(ans+max(dp2))