結果
問題 | No.1488 Max Score of the Tree |
ユーザー |
|
提出日時 | 2021-09-07 20:23:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 1,162 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 140,032 KB |
最終ジャッジ日時 | 2024-12-23 20:16:27 |
合計ジャッジ時間 | 6,187 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import sys sys.setrecursionlimit(10**6) n,k = map(int,input().split()) ab = [[] for i in range(n)] val = [] for i in range(n-1): a,b,c = map(int,input().split()) a -= 1 b -= 1 ab[a].append([b,i]) ab[b].append([a,i]) val.append(c) li = [0]*(n-1) def dfs(v,pre,idx): tmp = 0 for i in range(len(ab[v])): if ab[v][i][0] != pre: #print(ab[v][i]+1) dfs(ab[v][i][0],v,ab[v][i][1]) tmp += li[ab[v][i][1]] #print(ab[v],len(ab[v]),"len") if i == len(ab[v])-1: tmp -= 1 tmp = max(0,tmp) #print(v+1) li[idx] = tmp+1 #print(li,idx) #return tmp+1 for v,idx in ab[0]: #print(v,idx) dfs(v,0,idx) #print(li,"li") dp = [[0]*(k+1) for _ in range(n)] ans = 0 for i in range(n-1): ans += val[i]*li[i] for i in range(n-1): for j in range(k+1): if j-val[i] >= 0: dp[i+1][j] = max(dp[i][j-val[i]]+val[i]*li[i],dp[i][j]) else: dp[i+1][j] = dp[i][j] #for i in range(k+1): # add = max(add,dp[n-1][i]) #print(dp) add = dp[n-1][k] print(add+ans)