/* -*- coding: utf-8 -*- * * 778.cc: No.778 クリスマスツリー - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 200000; /* typedef */ typedef long long ll; typedef vector vi; template struct BIT { int n; T bits[MAX_N + 1]; BIT() {} void init(int _n) { n = _n; memset(bits, 0, sizeof(bits)); } T sum(int x) { T s = 0; while (x > 0) { s += bits[x]; x -= (x & -x); } return s; } void add(int x, T v) { while (x <= n) { bits[x] += v; x += (x & -x); } } }; /* global variables */ int prts[MAX_N], cis[MAX_N], avs[MAX_N]; vi clds[MAX_N]; BIT bit; /* subroutines */ /* main */ int main() { int n; scanf("%d", &n); prts[0] = -1; for (int i = 1; i < n; i++) { scanf("%d", prts + i); clds[prts[i]].push_back(i); } memset(cis, -1, sizeof(cis)); bit.init(n); ll sum = 0; for (int u = 0, rn = 0; u >= 0;) { if (cis[u] < 0) avs[u] = rn - bit.sum(u); if (++cis[u] >= clds[u].size()) { sum += (rn - bit.sum(u)) - avs[u]; bit.add(u + 1, 1); rn++; u = prts[u]; } else u = clds[u][cis[u]]; } printf("%lld\n", sum); return 0; }