結果
問題 |
No.763 Noelちゃんと木遊び
|
ユーザー |
![]() |
提出日時 | 2024-06-10 16:33:44 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 1,736 bytes |
コンパイル時間 | 15,581 ms |
コンパイル使用メモリ | 401,968 KB |
実行使用メモリ | 14,848 KB |
最終ジャッジ日時 | 2025-03-22 10:43:36 |
合計ジャッジ時間 | 18,634 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
use proconio::input; use proconio::marker::Usize1; fn main() { input! { n: usize, edges: [(Usize1, Usize1); n - 1], } let mut g = vec![Vec::new(); n]; for &(i, j) in &edges { g[i].push(j); g[j].push(i); } let mut sorted = Vec::new(); let mut parent = vec![usize::MAX; n]; let mut stack = vec![0]; while let Some(i) = stack.pop() { sorted.push(i); g[i].retain(|&j| j != parent[i]); for &j in &g[i] { stack.push(j); parent[j] = i; } } let o = O {}; let mut dp = vec![Value::default(); n]; for &i in sorted.iter().rev() { dp[i] = o.g(g[i] .iter() .fold(O::identity(), |acc, &j| O::mul(acc, o.f(dp[j])))); } let ans = dp[0].x.max(dp[0].y); println!("{ans}"); } struct O {} impl Op for O { type Acc = Acc; type Value = Value; fn f(&self, value: Value) -> Acc { Acc { a: value.x.max(value.y), b: value.x, } } fn g(&self, acc: Acc) -> Value { Value { x: acc.a, y: 1 + acc.b, } } fn identity() -> Acc { Acc { a: 0, b: 0 } } fn mul(lhs: Acc, rhs: Acc) -> Acc { Acc { a: lhs.a + rhs.a, b: lhs.b + rhs.b, } } } #[derive(Debug, Clone, Copy, PartialEq, Default)] struct Value { x: usize, y: usize, } #[derive(Debug, Clone, Copy, PartialEq, Default)] struct Acc { a: usize, b: usize, } trait Op { type Value; type Acc; fn f(&self, value: Value) -> Acc; fn g(&self, acc: Acc) -> Value; fn identity() -> Acc; fn mul(lhs: Acc, rhs: Acc) -> Acc; }