fn dfs(cur: usize, prev: usize, paths: &Vec>, costs: &mut Vec) -> usize { let mut ret = 1usize; for &(v, idx) in paths[cur].iter() { if v == prev { continue; } let val = dfs(v, cur, paths, costs); ret += val; costs[idx] = val; } ret } fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut paths = vec![vec![]; n]; for i in 0..n-1 { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = temp[0]-1; let b = temp[1]-1; paths[a].push((b, i)); paths[b].push((a, i)); } let mut costs = vec![0usize; n-1]; dfs(0, 0, &paths, &mut costs); let mut result = n*n; for i in 0..n-1 { result += costs[i] * (n-costs[i]) * 2; } println!("{}", result); }