// #[rustfmt::skip] // pub mod lib {pub use ac_library::*;pub use itertools::{join, Combinations, Itertools, MultiProduct, Permutations};pub use proconio::{input,marker::{Chars, Usize1}};pub use std::{cmp::*, collections::*, mem::swap};pub use regex::Regex;pub use superslice::Ext;pub use num_traits::{One, ToPrimitive, FromPrimitive, PrimInt};#[macro_export]macro_rules! degg {($($val:expr),+ $(,)?) => {println!("[{}:{}] {}",file!(),line!(),{let mut parts = Vec::new();$(parts.push(format!("{} = {:?}", stringify!($val), &$val));)+parts.join(", ")})}}} // use lib::*; use std::cmp::max; use proconio::{input, marker::Usize1}; fn dfs(v: usize, to: &Vec>, p: usize, dp: &mut Vec<(usize, usize)>) -> (usize, usize) { if dp[v] != (usize::MAX, usize::MAX) { return dp[v] } let mut is_leaf = true; let mut kesu = 0; let mut nokosu = 0; for &v2 in to[v].iter() { if p == v2 { continue; } is_leaf = false; let pre = dfs(v2, to, v, dp); kesu += max(pre.0, pre.1); nokosu += max(pre.0, pre.1 - 1); } if is_leaf { dp[v] = (0, 1); return dp[v] } dp[v] = (kesu, nokosu + 1); dp[v] } fn main() { input! { n: usize, uv: [(Usize1, Usize1); n - 1] } let mut to = vec![vec![]; n]; for &(u, v) in uv.iter() { to[u].push(v); to[v].push(u); } let mut dp = vec![(usize::MAX, usize::MAX); n]; let ans = dfs(0, &to, usize::MAX, &mut dp); println!("{}", max(ans.0, ans.1)); }