// The main code is at the very bottom. #[allow(unused_imports)] use { lib::byte::ByteChar, std::cell::{Cell, RefCell}, std::cmp::{ self, Ordering::{self, *}, Reverse, }, std::collections::*, std::convert::identity, std::fmt::{self, Debug, Display, Formatter}, std::io::prelude::*, std::iter::{self, FromIterator}, std::marker::PhantomData, std::mem, std::num::Wrapping, std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive}, std::process, std::rc::Rc, std::thread, std::time::{Duration, Instant}, std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize}, }; #[allow(unused_imports)] #[macro_use] pub mod lib { pub mod byte { pub use self::byte_char::*; mod byte_char { use std::error::Error; use std::fmt::{self, Debug, Display, Formatter}; use std::str::FromStr; #[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)] #[repr(transparent)] pub struct ByteChar(pub u8); impl Debug for ByteChar { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "b'{}'", self.0 as char) } } impl Display for ByteChar { fn fmt(&self, f: &mut Formatter) -> fmt::Result { write!(f, "{}", self.0 as char) } } impl FromStr for ByteChar { type Err = ParseByteCharError; fn from_str(s: &str) -> Result { match s.as_bytes().len() { 1 => Ok(ByteChar(s.as_bytes()[0])), 0 => Err(ParseByteCharErrorKind::EmptyStr.into()), _ => Err(ParseByteCharErrorKind::TooManyBytes.into()), } } } #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] pub struct ParseByteCharError { kind: ParseByteCharErrorKind, } impl Display for ParseByteCharError { fn fmt(&self, f: &mut Formatter) -> fmt::Result { f.write_str(match self.kind { ParseByteCharErrorKind::EmptyStr => "empty string", ParseByteCharErrorKind::TooManyBytes => "too many bytes", }) } } impl Error for ParseByteCharError {} #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] enum ParseByteCharErrorKind { EmptyStr, TooManyBytes, } impl From for ParseByteCharError { fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError { ParseByteCharError { kind } } } } } pub mod io { pub use self::scanner::*; mod scanner { use std::io::{self, BufRead}; use std::iter; use std::str::FromStr; #[derive(Debug)] pub struct Scanner { reader: R, buf: String, pos: usize, } impl Scanner { pub fn new(reader: R) -> Self { Scanner { reader, buf: String::new(), pos: 0, } } pub fn next(&mut self) -> io::Result<&str> { let start = loop { match self.rest().find(|c| c != ' ') { Some(i) => break i, None => self.fill_buf()?, } }; self.pos += start; let len = self.rest().find(' ').unwrap_or(self.rest().len()); let s = &self.buf[self.pos..][..len]; // self.rest()[..len] self.pos += len; Ok(s) } pub fn parse_next(&mut self) -> io::Result> where T: FromStr, { Ok(self.next()?.parse()) } pub fn parse_next_n(&mut self, n: usize) -> io::Result, T::Err>> where T: FromStr, { iter::repeat_with(|| self.parse_next()).take(n).collect() } pub fn map_next_bytes(&mut self, mut f: F) -> io::Result> where F: FnMut(u8) -> T, { Ok(self.next()?.bytes().map(&mut f).collect()) } pub fn map_next_bytes_n(&mut self, n: usize, mut f: F) -> io::Result>> where F: FnMut(u8) -> T, { iter::repeat_with(|| self.map_next_bytes(&mut f)) .take(n) .collect() } fn rest(&self) -> &str { &self.buf[self.pos..] } fn fill_buf(&mut self) -> io::Result<()> { self.buf.clear(); self.pos = 0; let read = self.reader.read_line(&mut self.buf)?; if read == 0 { return Err(io::ErrorKind::UnexpectedEof.into()); } if *self.buf.as_bytes().last().unwrap() == b'\n' { self.buf.pop(); } Ok(()) } } } } } #[allow(unused_macros)] macro_rules! eprint { ($($arg:tt)*) => { if cfg!(debug_assertions) { std::eprint!($($arg)*) } }; } #[allow(unused_macros)] macro_rules! eprintln { ($($arg:tt)*) => { if cfg!(debug_assertions) { std::eprintln!($($arg)*) } }; } #[allow(unused_macros)] macro_rules! dbg { ($($arg:tt)*) => { if cfg!(debug_assertions) { std::dbg!($($arg)*) } else { ($($arg)*) } }; } const CUSTOM_STACK_SIZE_MIB: Option = Some(1024); const INTERACTIVE: bool = false; fn main() -> std::io::Result<()> { match CUSTOM_STACK_SIZE_MIB { Some(stack_size_mib) => std::thread::Builder::new() .name("run_solver".to_owned()) .stack_size(stack_size_mib * 1024 * 1024) .spawn(run_solver)? .join() .unwrap(), None => run_solver(), } } fn run_solver() -> std::io::Result<()> { let stdin = std::io::stdin(); let reader = stdin.lock(); let stdout = std::io::stdout(); let writer = stdout.lock(); macro_rules! with_wrapper { ($($wrapper:expr)?) => {{ let mut writer = $($wrapper)?(writer); solve(reader, &mut writer)?; writer.flush() }}; } if cfg!(debug_assertions) || INTERACTIVE { with_wrapper!() } else { with_wrapper!(std::io::BufWriter::new) } } fn solve(reader: R, mut writer: W) -> std::io::Result<()> where R: BufRead, W: Write, { let mut _scanner = lib::io::Scanner::new(reader); #[allow(unused_macros)] macro_rules! scan { ($T:ty) => { _scanner.parse_next::<$T>()?.unwrap() }; ($($T:ty),+) => { ($(scan!($T)),+) }; ($T:ty; $n:expr) => { _scanner.parse_next_n::<$T>($n)?.unwrap() }; ($($T:ty),+; $n:expr) => { iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) }) .take($n) .collect::>>()? }; } #[allow(unused_macros)] macro_rules! scan_bytes_map { ($f:expr) => { _scanner.map_next_bytes($f)? }; ($f:expr; $n:expr) => { _scanner.map_next_bytes_n($n, $f)? }; } #[allow(unused_macros)] macro_rules! print { ($($arg:tt)*) => { write!(writer, $($arg)*)? }; } #[allow(unused_macros)] macro_rules! println { ($($arg:tt)*) => { writeln!(writer, $($arg)*)? }; } #[allow(unused_macros)] macro_rules! answer { ($($arg:tt)*) => {{ println!($($arg)*); return Ok(()); }}; } { let n = scan!(usize); let mut t = vec![vec![]; n]; for _ in 0..n - 1 { let (a, b) = scan!(usize, usize); let (a, b) = (a - 1, b - 1); t[a].push(b); t[b].push(a); } #[derive(Clone, Copy, Debug)] struct M { len: u64, sum: u64, } impl M { fn identity() -> Self { Self { len: 0, sum: 0 } } fn op(self, other: Self) -> Self { Self { len: self.len + other.len, sum: self.sum + other.sum, } } fn lift(self) -> Self { Self { len: self.len + 1, sum: self.sum + (self.len + 1), } } } fn scan(t: &[Vec], root: usize, par: Option, val: &mut [HashMap]) { let mut acc = M::identity(); for &i in &t[root] { if Some(i) == par { continue; } scan(t, i, Some(root), val); acc = acc.op(val[root][&i]); } if let Some(par) = par { val[par].insert(root, acc.lift()); } } fn calc( t: &[Vec], root: usize, par: Option, root_val: &mut [Option], val: &mut [HashMap], ) { let deg = t[root].len(); let mut r = Vec::with_capacity(deg); r.push(M { len: 0, sum: 0 }); for &i in t[root].iter().rev().take(deg - 1) { let x = val[root][&i]; let &y = r.last().unwrap(); r.push(x.op(y)); } let mut l = M { len: 0, sum: 0 }; for (&i, &r) in t[root].iter().zip(r.iter().rev()) { val[i].entry(root).or_insert(l.op(r).lift()); l = l.op(val[root][&i]); } root_val[root] = Some(l.lift()); for &i in &t[root] { if Some(i) == par { continue; } calc(t, i, Some(root), root_val, val); } } let mut val = (0..t.len()) .map(|i| HashMap::with_capacity(t[i].len())) .collect::>(); scan(&t, 0, None, &mut val); let mut root_val = vec![None; n]; calc(&t, 0, None, &mut root_val, &mut val); let ans = root_val.into_iter().map(|m| m.unwrap().sum).sum::(); println!("{}", ans); } #[allow(unreachable_code)] Ok(()) }