#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using i64 = int_fast64_t; using ui64 = uint_fast64_t; using db = long double; using pii = pair; using pli = pair; using pll = pair; using pdi = pair; template using vct = vector; template using heap = priority_queue; template using minheap = priority_queue, greater>; template constexpr T inf = numeric_limits::max() / 4 - 1; constexpr int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; constexpr int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; constexpr long double gold = 1.618033988; constexpr long double eps = 1e-15; #define mod 1000000007LL #define stdout_precision 10 #define stderr_precision 2 #define itr(i,v) for(auto i = begin(v); i != end(v); ++i) #define ritr(i,v) for(auto i = rbegin(v); i != rend(v); ++i) #define rep(i,n) for(int i = 0; i < (n); ++i) #define rrep(i,n) for(int i = (n) - 1; i >= 0; --i) #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define fir first #define sec second #define fro front #define bac back #define u_map unordered_map #define u_set unordered_set #define l_bnd lower_bound #define u_bnd upper_bound #define rsz resize #define ers erase #define emp emplace #define emf emplace_front #define emb emplace_back #define pof pop_front #define pob pop_back #define mkp make_pair #define mkt make_tuple #define popcnt __builtin_popcount struct setupper { setupper() { ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); std::cerr.tie(nullptr); std::cout << fixed << setprecision(stdout_precision); std::cerr << fixed << setprecision(stderr_precision); // #ifdef LOCAL // std::cerr << "\n---stderr---\n"; // auto print_atexit = []() { // std::cerr << "Exec time : " << clock() / (double)CLOCKS_PER_SEC * 1000.0 << "ms\n"; // std::cerr << "------------\n"; // }; // atexit((void(*)())print_atexit); // #endif } } setupper_; namespace std { template void hash_combine(size_t &seed, T const &key) { seed ^= hash()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } template struct hash> { size_t operator()(pair const &pr) const { size_t seed = 0; hash_combine(seed,pr.first); hash_combine(seed,pr.second); return seed; } }; template ::value - 1> struct hashval_calc { static void apply(size_t& seed, Tup const& tup) { hashval_calc::apply(seed, tup); hash_combine(seed,get(tup)); } }; template struct hashval_calc { static void apply(size_t& seed, Tup const& tup) { hash_combine(seed,get<0>(tup)); } }; template struct hash> { size_t operator()(tuple const& tup) const { size_t seed = 0; hashval_calc>::apply(seed,tup); return seed; } }; } template istream &operator>> (istream &s, pair &p) { return s >> p.first >> p.second; } template ostream &operator<< (ostream &s, const pair p) { return s << p.first << " " << p.second; } template ostream &operator<< (ostream &s, const vector &v) { for(size_t i = 0; i < v.size(); ++i) s << (i ? " " : "") << v[i]; return s; } #define dump(...) cerr << " [ " << __LINE__ << " : " << __FUNCTION__ << " ] " << #__VA_ARGS__ << " : ";\ dump_func(__VA_ARGS__) template void dump_func(T x) { cerr << x << '\n'; } template void dump_func(T x, Rest ... rest) { cerr << x << ","; dump_func(rest...); } template T read() { T x; return cin >> x, x; } template void write(T x) { cout << x << '\n'; } template void write(T x, Rest ... rest) { cout << x << ' '; write(rest...); } void writeln() {} template void writeln(T x, Rest ... rest) { cout << x << '\n'; writeln(rest...); } #define esc(...) writeln(__VA_ARGS__), exit(0) namespace updater { template static void add(T &x, const T &y) { x += y; } template static void ext_add(T &x, const T &y, size_t w) { x += y * w; } template static void mul(T &x, const T &y) { x *= y; } template static void ext_mul(T &x, const T &y, size_t w) { x *= (T)pow(y,w); } template static bool chmax(T &x, const T &y) { return x < y ? x = y,true : false; } template static bool chmin(T &x, const T &y) { return x > y ? x = y,true : false; } }; using updater::chmax; using updater::chmin; template T minf(const T &x, const T &y) { return min(x,y); } template T mixf(const T &x, const T &y) { return max(x,y); } bool bit(i64 n, uint8_t e) { return (n >> e) & 1; } i64 mask(i64 n, uint8_t e) { return n & ((1 << e) - 1); } int ilog(uint64_t x, uint64_t b = 2) { return x ? 1 + ilog(x / b,b) : -1; } template i64 binry(i64 ok, i64 ng, const F &fn) { while (abs(ok - ng) > 1) { i64 mid = (ok + ng) / 2; (fn(mid) ? ok : ng) = mid; } return ok; } template void init(A (&array)[N], const T &val) { fill((T*)array,(T*)(array + N),val); } template void cmprs(A ary[], size_t n) { vector tmp(ary,ary + n); tmp.erase(unique(begin(tmp),end(tmp)), end(tmp)); for(A *i = ary; i != ary + n; ++i) *i = l_bnd(all(tmp),*i) - begin(tmp); } template void cmprs(vector &v) { vector tmp = v; sort(begin(tmp),end(tmp)); tmp.erase(unique(begin(tmp),end(tmp)), end(tmp)); for(auto i = begin(v); i != end(v); ++i) *i = l_bnd(all(tmp),*i) - begin(tmp); } template void for_subset(uint_fast64_t s, const F &fn) { uint_fast64_t tmp = s; do { fn(tmp); } while((--tmp &= s) != s); } template struct Segtree { using opr_t = function; using update_opr_t = function; const opr_t opr; const update_opr_t update_opr; const Monoid idel; Monoid data[N << 1]; const size_t n; Segtree(size_t n_, Monoid idel_, const opr_t &opr_, const update_opr_t &update_opr_) : n(n_),opr(opr_),update_opr(update_opr_),idel(idel_) { fill(begin(data),end(data),idel); } template void copy(P s, P t) { for(size_t i = N; s != t; ++s, ++i) data[i] = *s; for(size_t i = N - 1; i; --i) data[i] = opr(data[i * 2],data[i * 2 + 1]); } template void copy(const A &v) { copy(begin(v),end(v)); } void update(size_t idx, T val) { update_opr(data[idx += N],val); while(idx >>= 1) data[idx] = opr(data[idx * 2],data[idx * 2 + 1]); } Monoid query(size_t a, size_t b, bool is_first = true) { if(a >= b) return idel; if(is_first) a += N,b += N; Monoid left = a & 1 ? data[a++] : idel; Monoid right = b & 1 ? data[--b] : idel; return opr(opr(left,query(a >> 1,b >> 1,false)),right); } size_t segbound(size_t i, const function &judge) { size_t w = 1,rig = i,j = N << 1; i += N; while(i != j) { if(i & 1) { rig += w; if(!judge(data[i],w)) break; i++; } i >>= 1,j >>= 1,w <<= 1; } if(i == j) return n; while(w > 1) { if(judge(data[i <<= 1],w >>= 1)) ++i; else rig -= w; } return min(n,--rig); } struct sum_lower_bound_fn { Monoid x; sum_lower_bound_fn(Monoid x_) : x(x_) {} bool operator()(Monoid v, size_t w) { return v < x ? x -= v,true : false; } }; size_t sum_lower_bound(size_t i, Monoid v) { return segbound(i, sum_lower_bound_fn(v)); } struct sum_upper_bound_fn { Monoid x; sum_upper_bound_fn(Monoid x_) : x(x_) {} bool operator()(Monoid v, size_t w) { return v <= x ? x -= v,true : false; } }; size_t sum_upper_bound(size_t i, Monoid v) { return segbound(i, sum_upper_bound_fn(v)); } }; int n; int a[1<<18]; vector G[1<<18]; i64 ans; Segtree sg( 200010,0, plus(), updater::add ); void dfs(int v) { ans+=sg.query(0,v); sg.update(v,1); for(int i:G[v]) { dfs(i); } sg.update(v,-1); } signed main() { cin>>n; rep(i,n-1) { int a; cin>>a; G[a].emplace_back(i+1); } dfs(0); writeln(ans); }