// Bundled at 2024/09/03 19:20:39 +09:00 // Author: Haar pub mod main { use super::*; use haar_lib::{ get, input, tree::{tree_dp::*, *}, utils::fastio::*, utils::join_str::*, }; #[allow(unused_imports)] use std::cell::RefCell; use std::cmp::max; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet}; #[allow(unused_imports)] use std::io::Write; #[allow(unused_imports)] use std::rc::Rc; #[derive(Clone, Default)] pub struct Problem {} impl Problem { pub fn main(&mut self) -> Result<(), Box> { let mut io = FastIO::new(); let n = io.read_usize(); let mut builder = TreeBuilder::new(n); for _ in 0..n - 1 { let u = io.read_usize() - 1; let v = io.read_usize() - 1; builder.extend(Some(TreeEdge::new(u, v, (), ()))); } let tree = builder.build(); let id = (0, 0); let up = Box::new(|a: (u64, u64), _| a); let merge = Box::new(|a: (u64, u64), b: (u64, u64)| { (a.0 + max(b.0 - 1, b.1), a.1 + max(b.0, b.1)) }); let apply = Box::new(|a: (u64, u64), _| (a.0 + 1, a.1)); let dp = TreeDP::new(id, merge, up, apply); let dp = dp.run(&tree, 0); let ans = max(dp[0].0, dp[0].1); io.writeln(ans); Ok(()) } } } fn main() { main::Problem::default().main().unwrap(); } use crate as haar_lib; pub mod macros { pub mod io { #[macro_export] macro_rules! get { ( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => { { let n = $num; (0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::>() } }; ( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => { ($(get!($in, $type $(as $to)*)),*) }; ( $in:ident, i8 ) => { $in.read_i64() as i8 }; ( $in:ident, i16 ) => { $in.read_i64() as i16 }; ( $in:ident, i32 ) => { $in.read_i64() as i32 }; ( $in:ident, i64 ) => { $in.read_i64() }; ( $in:ident, isize ) => { $in.read_i64() as isize }; ( $in:ident, u8 ) => { $in.read_u64() as u8 }; ( $in:ident, u16 ) => { $in.read_u64() as u16 }; ( $in:ident, u32 ) => { $in.read_u64() as u32 }; ( $in:ident, u64 ) => { $in.read_u64() }; ( $in:ident, usize ) => { $in.read_u64() as usize }; ( $in:ident, [char] ) => { $in.read_chars() }; ( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) }; } #[macro_export] macro_rules! input { ( @inner $in:ident, mut $name:ident : $type:tt ) => { let mut $name = get!($in, $type); }; ( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => { let mut $name = get!($in, $type as $to); }; ( @inner $in:ident, $name:ident : $type:tt ) => { let $name = get!($in, $type); }; ( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => { let $name = get!($in, $type as $to); }; ( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => { $(input!(@inner $in, $($names)* : $type $(as $to)*);)* } } } } pub mod tree { pub mod tree_dp { use crate::tree::*; pub struct TreeDP<'a, Weight, T> { id: T, merge: Box T>, up: Box T>, apply: Box T>, } impl<'a, Weight, T> TreeDP<'a, Weight, T> where Weight: Copy, T: Clone, { pub fn new( id: T, merge: Box T>, up: Box T>, apply: Box T>, ) -> Self { Self { id, merge, up, apply, } } pub fn run>( &self, tree: &Tree, root: usize, ) -> Vec { let size = tree.len(); let mut ret = vec![self.id.clone(); size]; self.__dfs(tree, root, None, &mut ret); ret } fn __dfs>( &self, tree: &Tree, cur: usize, par: Option, ret: &mut Vec, ) { for e in tree.nodes[cur].neighbors() { if Some(e.to()) == par { continue; } self.__dfs(tree, e.to(), Some(cur), ret); let temp = (self.up)(ret[e.to()].clone(), (e.to(), e.weight())); ret[cur] = (self.merge)(ret[cur].clone(), temp); } ret[cur] = (self.apply)(ret[cur].clone(), cur); } } } pub trait TreeEdgeTrait { type Weight; fn from(&self) -> usize; fn to(&self) -> usize; fn weight(&self) -> Self::Weight; fn rev(self) -> Self; } #[derive(Clone, Debug)] pub struct TreeEdge { pub from: usize, pub to: usize, pub weight: T, pub index: I, } impl TreeEdge { pub fn new(from: usize, to: usize, weight: T, index: I) -> Self { Self { from, to, weight, index, } } } impl TreeEdgeTrait for TreeEdge { type Weight = T; #[inline] fn from(&self) -> usize { self.from } #[inline] fn to(&self) -> usize { self.to } #[inline] fn weight(&self) -> Self::Weight { self.weight.clone() } fn rev(mut self) -> Self { std::mem::swap(&mut self.from, &mut self.to); self } } #[derive(Clone, Debug, Default)] pub struct TreeNode { pub parent: Option, pub children: Vec, } impl TreeNode { pub fn neighbors(&self) -> impl DoubleEndedIterator { self.children.iter().chain(self.parent.iter()) } pub fn neighbors_size(&self) -> usize { self.children.len() + self.parent.as_ref().map_or(0, |_| 1) } } pub struct TreeBuilder { nodes: Vec>, } impl TreeBuilder { pub fn new(size: usize) -> Self { Self { nodes: vec![ TreeNode { parent: None, children: vec![], }; size ], } } pub fn extend(&mut self, edges: impl IntoIterator) { for e in edges { self.nodes[e.from()].children.push(e.clone()); self.nodes[e.to()].children.push(e.rev()); } } pub fn build(self) -> Tree { Tree { nodes: self.nodes, root: None, } } } pub struct RootedTreeBuilder { nodes: Vec>, root: usize, } impl RootedTreeBuilder { pub fn new(size: usize, root: usize) -> Self { Self { nodes: vec![ TreeNode { parent: None, children: vec![], }; size ], root, } } pub fn extend(&mut self, edges: impl IntoIterator) { for e in edges { assert!(self.nodes[e.to()].parent.is_none()); self.nodes[e.from()].children.push(e.clone()); self.nodes[e.to()].parent.replace(e.rev()); } } pub fn build(self) -> Tree { Tree { nodes: self.nodes, root: Some(self.root), } } } #[derive(Clone, Debug)] pub struct Tree { nodes: Vec>, root: Option, } impl Tree { pub fn nodes_iter(&self) -> impl Iterator> { self.nodes.iter() } pub fn len(&self) -> usize { self.nodes.len() } pub fn is_empty(&self) -> bool { self.nodes.is_empty() } pub fn root(&self) -> Option { self.root } } } pub mod utils { pub mod fastio { use std::fmt::Display; use std::io::{Read, Write}; pub struct FastIO { in_bytes: Vec, in_cur: usize, out_buf: std::io::BufWriter, } impl FastIO { pub fn new() -> Self { let mut s = vec![]; std::io::stdin().read_to_end(&mut s).unwrap(); let cout = std::io::stdout(); Self { in_bytes: s, in_cur: 0, out_buf: std::io::BufWriter::new(cout), } } #[inline] pub fn getc(&mut self) -> Option { if self.in_cur < self.in_bytes.len() { self.in_cur += 1; Some(self.in_bytes[self.in_cur]) } else { None } } #[inline] pub fn peek(&self) -> Option { if self.in_cur < self.in_bytes.len() { Some(self.in_bytes[self.in_cur]) } else { None } } #[inline] pub fn skip(&mut self) { while self.peek().map_or(false, |c| c.is_ascii_whitespace()) { self.in_cur += 1; } } pub fn read_u64(&mut self) -> u64 { self.skip(); let mut ret: u64 = 0; while self.peek().map_or(false, |c| c.is_ascii_digit()) { ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64; self.in_cur += 1; } ret } pub fn read_u32(&mut self) -> u32 { self.read_u64() as u32 } pub fn read_usize(&mut self) -> usize { self.read_u64() as usize } pub fn read_i64(&mut self) -> i64 { self.skip(); let mut ret: i64 = 0; let minus = if self.peek() == Some(b'-') { self.in_cur += 1; true } else { false }; while self.peek().map_or(false, |c| c.is_ascii_digit()) { ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64; self.in_cur += 1; } if minus { ret = -ret; } ret } pub fn read_i32(&mut self) -> i32 { self.read_i64() as i32 } pub fn read_isize(&mut self) -> isize { self.read_i64() as isize } pub fn read_f64(&mut self) -> f64 { self.read_chars() .into_iter() .collect::() .parse() .unwrap() } pub fn read_chars(&mut self) -> Vec { self.skip(); let mut ret = vec![]; while self.peek().map_or(false, |c| c.is_ascii_graphic()) { ret.push(self.in_bytes[self.in_cur] as char); self.in_cur += 1; } ret } pub fn write_rev(&mut self, s: T) { let mut s = format!("{}", s); let s = unsafe { s.as_bytes_mut() }; s.reverse(); self.out_buf.write_all(s).unwrap(); } pub fn write(&mut self, s: T) { self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap(); } pub fn writeln_rev(&mut self, s: T) { self.write_rev(s); self.out_buf.write_all(&[b'\n']).unwrap(); } pub fn writeln(&mut self, s: T) { self.write(s); self.out_buf.write_all(&[b'\n']).unwrap(); } } impl Drop for FastIO { fn drop(&mut self) { self.out_buf.flush().unwrap(); } } } pub mod join_str { pub trait JoinStr { fn join_str(self, _: &str) -> String; } impl JoinStr for I where T: ToString, I: Iterator, { fn join_str(self, s: &str) -> String { self.map(|x| x.to_string()).collect::>().join(s) } } } }