use std::collections::BinaryHeap; 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[v] += 1; indegs[u] += 1; } let mut ans = 1; let mut pq = (0..n).map(|i| (indegs[i], i)).collect::>(); let mut deled = vec![false; n]; while let Some((indeg, crr)) = pq.pop() { if indegs[crr] < indeg || indeg <= 1 { continue; } deled[crr] = true; ans += indeg - 1; // println!("indeg:{} crr:{} ans:{}",indeg,crr,ans); for &nxt in g[crr].iter() { if deled[nxt] { continue; } indegs[nxt] -= 1; pq.push((indegs[nxt], nxt)); } } println!("{}", ans); }