結果
問題 |
No.1488 Max Score of the Tree
|
ユーザー |
|
提出日時 | 2022-09-01 21:47:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 174 ms / 2,000 ms |
コード長 | 1,036 bytes |
コンパイル時間 | 303 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 73,724 KB |
最終ジャッジ日時 | 2024-11-14 13:38:29 |
合計ジャッジ時間 | 4,772 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
N,K = map(int,input().split()) e = [[] for _ in range(N)] edge = dict() I = 0 for _ in range(N-1): a,b,c = map(int,input().split()) a -= 1 b -= 1 e[a].append(b) e[b].append(a) edge[(a,b)]=c edge[(b,a)]=c depth = [-1]*N leaves = [-1]*N depth[0] = 0 for i in range(1,N): if len(e[i])==1: leaves[i] = 1 def dfs(x): if leaves[x] !=-1: return leaves[x] tmp = 0 for ix in e[x]: if depth[ix]==-1: depth[ix] = depth[x]+1 for ix in e[x]: if depth[ix]>depth[x]: tmp += dfs(ix) leaves[x] = tmp return tmp dfs(0) E = [] for i in range(N): for j in e[i]: if depth[j]<depth[i]: c = edge[(i,j)] E.append((c,c*leaves[i])) I += c*leaves[i] break N = len(E) dp = [0]*(K+2) for i in range(N): a,b = E[i] for j in range(K,-1,-1): dp[min(j+a,K+1)] = max(dp[j] + b,dp[min(j+a,K+1)]) print(max(dp[:K+1])+I)