use std::collections::BTreeSet; use proconio::{input, marker::Usize1}; fn main() { input! { n:usize, uv:[(Usize1,Usize1);n-1], } let mut indegs = vec![0;n]; let mut g = vec![vec![]; n]; for &(u, v) in uv.iter() { g[u].push(v); g[v].push(u); indegs[u]+=1; indegs[v]+=1; } let mut st=(0..n).map(|i|(indegs[i],i)).collect::>(); let mut deled = vec![false; n]; while let Some((indeg, crr)) = st.pop_last() { if indeg <= 1 { continue; } deled[crr] = true; for &nxt in g[crr].iter() { if deled[nxt] { continue; } st.remove(&(indegs[nxt],nxt)); indegs[nxt] -= 1; st.insert((indegs[nxt], nxt)); } } let ans=deled.iter().filter(|&&del|!del).count()-(0..n).filter(|&i|!deled[i]&&indegs[i]>=1).count()/2; println!("{}", ans); }