fn dfs(cur: usize, parent: usize, edges: &Vec>, tour: &mut Vec) { tour.push(cur); for &to in edges[cur].iter().filter(|&&x| x != parent) { dfs(to, cur, edges, tour); } tour.push(cur); } fn main() { let n = read::(); let a = read_vec::(); let mut seg = SegTree::new(2 * n, 0i64, |x, y| x + y); let mut edges = vec![vec![]; n]; for i in 0..n - 1 { edges[i + 1].push(a[i]); edges[a[i]].push(i + 1); } let mut tour = vec![]; dfs(0, 0, &edges, &mut tour); let mut pre_order = vec![0; n]; let mut post_order = vec![0; n]; for i in (0..tour.len()).rev() { pre_order[tour[i]] = i; } for i in 0..tour.len() { post_order[tour[i]] = i; } let mut ans = 0; for i in (0..n).rev() { ans += seg.query(pre_order[i], post_order[i] + 1); seg.update(pre_order[i], 1); } println!("{}", ans); } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Clone)] struct SegTree where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { n: usize, dat: Vec, init: T, functor: F, } impl SegTree where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { fn new(n: usize, init: T, f: F) -> SegTree { let mut m = 1; // For simplicity, we use 2 ** n sized SegTree. while m < n { m *= 2; } SegTree { n: m, dat: vec![init; 2 * m - 1], init: init, functor: f, } } // dat[k] = a; fn update(&mut self, k: usize, a: T) { let mut k = k; k += self.n - 1; self.dat[k] = a; while k > 0 { k = (k - 1) / 2; self.dat[k] = (self.functor)(self.dat[k * 2 + 1], self.dat[k * 2 + 2]); } } // [a, b) fn query(&self, a: usize, b: usize) -> T { self.query_inner(a, b, 0, 0, self.n) } fn query_inner(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T { if r <= a || b <= l { return self.init; } if a <= l && r <= b { return self.dat[k]; } let vl = self.query_inner(a, b, k * 2 + 1, l, (l + r) / 2); let vr = self.query_inner(a, b, k * 2 + 2, (l + r) / 2, r); (self.functor)(vl, vr) } }