use proconio::{input, marker::Usize1}; fn main() { input! { n:usize, uv:[(Usize1,Usize1);n-1], } let mut g = vec![vec![]; n]; for &(u, v) in uv.iter() { g[u].push(v); g[v].push(u); } let mut childs = vec![0; n]; let mut dp = vec![0; n]; f(0, n, n, &g, &mut childs, &mut dp); let ans = dp.iter().sum::(); println!("{}", ans); } fn f( crr: usize, prv: usize, n: usize, g: &Vec>, childs: &mut Vec, dp: &mut Vec, ) { for &nxt in g[crr].iter() { if nxt == prv { continue; } f(nxt, crr, n, g, childs, dp); childs[crr] += childs[nxt]; dp[crr] += childs[nxt] * (n - childs[nxt]); } childs[crr] += 1; dp[crr] += (n - childs[crr]) * childs[crr]; dp[crr] += n; }