#include #include #include #include #include #include #include #define REP(i, a, b) for (int i = int(a); i < int(b); i++) using namespace std; using ll = long long int; using P = pair; // clang-format off #ifdef _DEBUG_ #define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false) template void PPPPP(T t) { cerr << t; } template void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); } #else #define dump(...) do{ } while(false) #endif template vector make_v(size_t a, T b) { return vector(a, b); } template auto make_v(size_t a, Ts... ts) { return vector(a, make_v(ts...)); } template bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; } template bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; } template void print(T a) { cout << a << endl; } template void print(T a, Ts... ts) { cout << a << ' '; print(ts...); } template istream &operator,(istream &in, T &t) { return in >> t; } // clang-format on #include template class SegmentTreeOneAll { using Func = function; public: vector data; int n; T init; Func update_func; Func query_func; SegmentTreeOneAll(int _n, T _init, Func up, Func qu) { init = _init; update_func = up; query_func = qu; for (n = 1; n < _n; n *= 2) ; data.resize(2 * n - 1, init); } void update(int pos, T val) { pos += n - 1; data[pos] = update_func(data[pos], val); while (pos > 0) { pos = (pos - 1) / 2; data[pos] = query_func(data[2 * pos + 1], data[2 * pos + 2]); } } T query(int l, int r) { T resL = init, resR = init; for (l += n - 1, r += n - 1; l < r; l = l / 2, r = (r - 1) / 2) { if (!(l & 1)) { resL = query_func(resL, data[l]); } if (!(r & 1)) { resR = query_func(data[r - 1], resR); } } return query_func(resL, resR); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin, n; vector> T(n); REP(i, 1, n) { int a; cin, a; T[a].push_back(i); } auto SUM = [](ll a, ll b) { return a + b; }; SegmentTreeOneAll seg(n, 0, SUM, SUM); function dfs = [&](int v) { ll res = seg.query(0, v); seg.update(v, 1); for (auto vv : T[v]) { res += dfs(vv); } seg.update(v, -1); return res; }; cout << dfs(0) << endl; return 0; }