#![allow(unused_imports)] use std::io::{ self, Write }; use std::str::FromStr; use std::cmp::{ min, max }; use std::collections::{ BinaryHeap, VecDeque }; #[allow(unused_macros)] macro_rules! trace { ($var:expr) => { let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var); }; ($($args:expr),*) => { trace!(($($args),*)) } } #[allow(unused_macros)] macro_rules! put { ($var:expr) => { let _ = writeln!(&mut std::io::stdout(), "{}", $var); }; ($var:expr, $($args:expr),*) => { let _ = write!(&mut std::io::stdout(), "{} ", $var); put!($($args),*); }; } use std::ops::Range; struct BIT { size: usize, array: Vec } #[allow(dead_code)] impl BIT { fn new(n: usize) -> BIT { BIT { size: n, array: vec![0; n + 1] } } fn add(&mut self, idx: usize, w: i32) { let mut x = idx + 1; while x <= self.size { self.array[x] += w; let xi = x as i32; x += (xi&-xi) as usize; } } fn sum_up(&self, idx: usize) -> i32 { // [0, idx) let mut sum = 0; let mut x = idx; while x > 0 { sum += self.array[x]; let xi = x as i32; x -= (xi&-xi) as usize; } sum } fn sum(&self, range: Range) -> i32 { self.sum_up(range.end) - self.sum_up(range.start) } } fn main() { let mut sc = Scanner::new(); let n: usize = sc.cin(); let mut bit = BIT::new(n); let mut tree = vec![vec![]; n]; for i in 1..n { let a: usize = sc.cin(); tree[a].push(i); } let mut stack = vec![(true, 0)]; let mut ans = 0u64; while let Some((dir, u)) = stack.pop() { if dir { ans += bit.sum_up(u) as u64; bit.add(u, 1); stack.push((false, u)); for &v in tree[u].iter() { stack.push((true, v)); } } else { bit.add(u, -1); } } put!(ans); } #[allow(dead_code)] struct Scanner { stdin: io::Stdin, buffer: VecDeque, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } } fn reserve(&mut self) { while self.buffer.len() == 0 { let mut line = String::new(); let _ = self.stdin.read_line(&mut line); for w in line.split_whitespace() { self.buffer.push_back(String::from(w)); } } } fn cin(&mut self) -> T { self.reserve(); match self.buffer.pop_front().unwrap().parse::() { Ok(a) => a, Err(_) => panic!("parse err") } } }