結果
問題 |
No.1488 Max Score of the Tree
|
ユーザー |
|
提出日時 | 2022-11-04 12:29:56 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,584 bytes |
コンパイル時間 | 13,138 ms |
コンパイル使用メモリ | 402,076 KB |
実行使用メモリ | 80,384 KB |
最終ジャッジ日時 | 2025-03-14 23:32:21 |
合計ジャッジ時間 | 16,112 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
fn dfs(cur: usize, prev: usize, paths: &Vec<Vec<(usize, usize)>>, leaves: &mut Vec<usize>) -> usize { let mut flg = false; let mut ret = 0usize; for &(v, _) in paths[cur].iter() { if v == prev { continue; } flg = true; ret += dfs(v, cur, paths, leaves); } if !flg { ret += 1; } leaves[cur] = ret; ret } fn main() { let mut nk = String::new(); std::io::stdin().read_line(&mut nk).ok(); let nk: Vec<usize> = nk.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nk[0]; let k = nk[1]; let mut lines = Vec::with_capacity(n-1); let mut paths = vec![vec![]; n]; for _ in 0..n-1 { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = temp[0]-1; let b = temp[1]-1; let c = temp[2]; paths[a].push((b, c)); paths[b].push((a, c)); lines.push((a, b, c)); } let mut leaves = vec![0usize; n]; dfs(0, 0, &paths, &mut leaves); let mut dp = vec![vec![0usize; k+1]; n]; let mut score = 0usize; for i in 0..n-1 { let (a, b, c) = lines[i]; let addval = c * leaves[a].min(leaves[b]); score += addval; for j in 0..=k { dp[i+1][j] = dp[i+1][j].max(dp[i][j]); if j+c <= k { dp[i+1][j+c] = dp[i+1][j+c].max(dp[i][j] + addval); } } } println!("{}", dp[n-1][k] + score); }