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 dp = tree_dp(&O {}, &g, &sorted); let ans = dp[0].retain.max(dp[0].remove); println!("{ans}"); } #[derive(Debug, Clone, PartialEq, Default)] struct Value { retain: usize, remove: usize, } #[derive(Debug, Clone, PartialEq, Default)] struct Acc { any_sum: usize, remove_sum: usize, } struct O {} impl Op for O { type Acc = Acc; type Value = Value; fn f(&self, value: &Self::Value, _index: usize) -> Self::Acc { Self::Acc { any_sum: value.retain.max(value.remove), remove_sum: value.remove, } } fn mul(&self, lhs: &Self::Acc, rhs: &Self::Acc, _parent: usize) -> Self::Acc { Self::Acc { any_sum: lhs.any_sum + rhs.any_sum, remove_sum: lhs.remove_sum + rhs.remove_sum, } } fn identity(&self, _parent: usize) -> Self::Acc { Self::Acc { any_sum: 0, remove_sum: 0, } } fn g(&self, acc: &Self::Acc, _index: usize) -> Self::Value { Self::Value { retain: 1 + acc.remove_sum, remove: acc.any_sum, } } } pub trait Op { type Value: Default + Clone; type Acc: Default + Clone; fn f(&self, value: &Self::Value, index: usize) -> Self::Acc; fn mul(&self, lhs: &Self::Acc, rhs: &Self::Acc, parent: usize) -> Self::Acc; fn identity(&self, parent: usize) -> Self::Acc; fn g(&self, acc: &Self::Acc, index: usize) -> Self::Value; } pub fn tree_dp(o: &O, g: &[Vec], sorted: &[usize]) -> Vec { let mut dp = vec![O::Value::default(); g.len()]; for &i in sorted.iter().rev() { dp[i] = o.g( &g[i] .iter() .fold(o.identity(i), |acc, &j| o.mul(&acc, &o.f(&dp[j], j), i)), i, ); } dp }