#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define DEBUG_ //!!提出時にコメントアウト!! #ifdef DEBUG_ #define dump(x) cerr << #x << " = " << (x) << endl; #else #define dump(x) ; #endif #define equals(a,b) (fabs((a)-(b)) < EPS) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define SZ(x) ((int)(x).size()) #define pb push_back #define eb emplace_back //#define int long long typedef long long LL; typedef vector VI; typedef vector VL; typedef vector VVI; typedef vector VVL; typedef vector VS; typedef pair PII; typedef pair PLL; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b std::string printVector(const std::vector &data) { std::stringstream ss; std::ostream_iterator out_it(ss, ", "); ss << "["; std::copy(data.begin(), data.end() - 1, out_it); ss << data.back() << "]"; return ss.str(); } template void print_array(const T &ary, int size){ REP(i,size){ cout << ary[i] << " "; } cout << endl; } const int mod = 1e9+7; //const int mod = 998244353; const LL LINF = 1001002003004005006ll; const int INF = 1001001001; const double EPS = (1e-10); const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899; int dx[] = {0,0,-1,1}; int dy[] = {-1,1,0,0}; template< typename Monoid > struct SegmentTree { using F = function< Monoid(Monoid, Monoid) >; int sz; vector< Monoid > seg; const F f; const Monoid M1; SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x) { seg[k + sz] = x; } void build() { for(int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } void update(int k, const Monoid &x) { k += sz; seg[k] = x; while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid query(int a, int b) { Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const { return seg[k + sz]; } }; VVI g; VI in,out; int timer = 0; void dfs(int v, int p){ in[v] = timer; for(int u : g[v]){ if(u == p) continue; timer++; dfs(u,v); } timer++; out[v] = timer; } signed main(int argc, char const *argv[]) { cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(12); int N; cin >> N; g.resize(N); in.resize(N); out.resize(N); FOR(i,1,N){ int a; cin >> a; g[i].eb(a); g[a].eb(i); } dfs(0,-1); auto f = [](LL a, LL b){return a+b;}; SegmentTree seg(timer+10, f, 0); LL ans = 0; for(int i = N-1; i >= 0; i--){ ans += seg.query(in[i], out[i]); seg.update(in[i], seg[in[i]]+1); } cout << ans << endl; //REP(i,N){ // cout << in[i] << " " << out[i] << endl; //} }