結果
問題 |
No.1488 Max Score of the Tree
|
ユーザー |
|
提出日時 | 2024-08-29 11:25:47 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 1,246 bytes |
コンパイル時間 | 13,081 ms |
コンパイル使用メモリ | 389,644 KB |
実行使用メモリ | 80,256 KB |
最終ジャッジ日時 | 2024-08-29 11:26:24 |
合計ジャッジ時間 | 16,423 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
use proconio::{input, marker::Usize1}; fn main() { input! { n:usize, k:usize, uvw:[(Usize1,Usize1,usize);n-1], } let mut g = vec![vec![]; n]; for &(u, v, _) in uvw.iter() { g[u].push(v); g[v].push(u); } let mut deps = vec![0; n]; let mut leefs = vec![0; n]; f(0, n, 0, &g, &mut deps, &mut leefs); let mut dp = vec![vec![0; k + 1]; n]; for (i, &(u, v, w)) in uvw.iter().enumerate() { for j in 0..=k { let r = if deps[u] < deps[v] { v } else { u }; dp[i + 1][j] = dp[i + 1][j].max(dp[i][j] + w * leefs[r]); if j + w <= k { dp[i + 1][j + w] = dp[i + 1][j + w].max(dp[i][j] + 2 * w * leefs[r]); } } } let ans = *dp[n - 1].iter().max().unwrap(); println!("{}", ans); } fn f( crr: usize, prv: usize, dep: usize, g: &Vec<Vec<usize>>, deps: &mut Vec<usize>, leefs: &mut Vec<usize>, ) { deps[crr] = dep; for &nxt in g[crr].iter() { if nxt == prv { continue; } f(nxt, crr, dep + 1, g, deps, leefs); leefs[crr] += leefs[nxt]; } if crr != 0 && g[crr].len() == 1 { leefs[crr] = 1; } }