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].x.max(dp[0].y); println!("{ans}"); } #[derive(Debug, Clone, Copy, PartialEq, Default)] struct Value { x: usize, y: usize, } #[derive(Debug, Clone, Copy, PartialEq, Default)] struct Acc { a: usize, b: usize, } 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, } } } pub trait Op { type Value: Default + Clone; type Acc; fn f(&self, value: &Self::Value) -> Self::Acc; fn g(&self, acc: &Self::Acc) -> Self::Value; fn identity() -> Self::Acc; fn mul(lhs: &Self::Acc, rhs: &Self::Acc) -> Self::Acc; } 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(), |acc, &j| O::mul(&acc, &o.f(&dp[j])))); } dp }