fn solve() { let (a, b, c): (usize, usize, usize) = (read(), read(), read()); println!("{:?}", a + b + c); let s: String = read(); println!("{:?}", s); } fn dfs(u: usize, p: usize, adjl: &Vec>, dp: &mut Vec>) { let mut leaf = true; // 残した時に消える個数 for &v in &adjl[u] { if v == p { continue; } leaf = false; dfs(v, u, adjl, dp); // 残した方が良い子を数える. dp[0][u] += max(dp[0][v] - 1, dp[1][v]); dp[1][u] += max(dp[0][v], dp[1][v]); } if leaf { dp[0][u] = 1; } } fn main() { let n = read(); let mut adjl: Vec> = vec![vec![]; n]; for _ in 0..n - 1 { let (mut x, mut y): (usize, usize) = (read::(), read::()); x -= 1; y -= 1; adjl[x].push(y); adjl[y].push(x); } // dp[0][i] ... i番目を消す // dp[1][u] ... 1番目を残す let mut dp = vec![vec![1; n]; 2]; dfs(0, 0, &adjl, &mut dp); println!("{}", max(dp[0][0], dp[1][0])); } // ========= #[allow(unused_imports)] use std::cmp::{max, min, Reverse}; #[allow(unused_imports)] use std::collections::{BinaryHeap, HashMap, HashSet}; #[allow(unused_imports)] use std::process::exit; #[allow(dead_code)] const MOD: usize = 1000000007; fn read() -> T { use std::io::Read; let stdin = std::io::stdin(); let stdin = stdin.lock(); let token: String = stdin .bytes() .map(|c| c.expect("failed to read char") as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect(); token.parse().ok().expect("failed to parse token") } // =========