use std::io::*; // 0を根とした各部分木のサイズ fn dfs1(v: usize, p: usize, sz: &mut Vec, g: &Vec>) -> usize { for &nv in g[v].iter() { if nv != p { sz[v] += dfs1(nv, v, sz, &g); } } sz[v] } // vを根とした状態になってる fn dfs2(v: usize, p: usize, sz: &mut Vec, ans: &mut Vec, g: &Vec>) { for &nv in g[v].iter() { ans[v] += (g.len() - sz[nv]) * sz[nv]; } for &nv in g[v].iter() { if nv != p { sz[v] -= sz[nv]; sz[nv] += sz[v]; dfs2(nv, v, sz, ans, &g); sz[nv] -= sz[v]; sz[v] += sz[nv]; } } } fn main() { let mut s: String = String::new(); std::io::stdin().read_to_string(&mut s).ok(); let mut itr = s.trim().split_whitespace(); let n: usize = itr.next().unwrap().parse().unwrap(); let mut g: Vec> = vec![Vec::new(); n]; for _ in 0..n - 1 { let a: usize = itr.next().unwrap().parse::().unwrap() - 1; let b: usize = itr.next().unwrap().parse::().unwrap() - 1; g[a].push(b); g[b].push(a); } let mut ans = vec![0; n]; let mut size = vec![1; n]; dfs1(0, 0, &mut size, &g); dfs2(0, 0, &mut size, &mut ans, &g); let s: usize = ans.iter().sum(); println!("{}", s + n * n); }