#include using namespace std; // #define int long long #define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i) #define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i) #define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--) #define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--) #define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i) #define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i) #define SORT(v, n) sort(v, v + n); #define REVERSE(v, n) reverse(v, v+n); #define vsort(v) sort(v.begin(), v.end()); #define all(v) v.begin(), v.end() #define mp(n, m) make_pair(n, m); #define cout(d) cout<; using vvi = vector; using vll = vector; using vvll = vector; using pii = pair; using pll = pair; using vs = vector; using vpll = vector>; using vtp = vector>; using vb = vector; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const ll INF = 1e9; const ll MOD = 1e9+7; const ll LINF = 1e18; template struct BIT { int n; vector d; BIT(int n=0):n(n),d(n+1) {} void add(int i, T x=1) { for (; i <= n; i += i&-i) { d[i] += x; } } T sum(int i) { T x = 0; for (; i; i -= i&-i) { x += d[i]; } return x; } T sum(int l, int r) { return sum(r) - sum(l-1); } }; BIT bit(200100); vll G[200100]; ll ans=0; void dfs(ll v){ ans+=bit.sum(v); bit.add(v+1); for(auto nv: G[v]) dfs(nv); // NOTE: ここでv+1に-1を加算する理由 // まず与えられたグラフが枝分かれしていない(つまり一本の線)場合は、 // 頂点0からdfsしていき、BITを使って今のノードより小さいノードの和を加算していけばよい // ここで、グラフのどこかで枝分かれがある場合を考える // 一方の枝において"今の頂点より小さい頂点の和"の総数をカウントする過程で、その枝の頂点をBITに加えていく訳だが、 // 何もしないままだと、1つ目の枝の探索を終えて、2つ目の枝を探索をする時には、BITには2つ目の枝とは関係無い1つ目の枝の頂点が残ったままの状態になる // 2つ目の枝に移る前に1つ目の枝の頂点をBITから除外しておきたいわけだが、そのために bit.add(v+1,-1) という処理が必要 // dfsはある枝において葉まで探索を終えると順に元の頂点へ戻っていき、枝分かれがある頂点から再度葉まで探索する、を繰り返す // よって、dfsの末尾にその頂点をBITから除外する処理を記述することで、次の枝に移る際には隣の枝にある頂点の情報はBITから消えていることになる bit.add(v+1,-1); } signed main() { cin.tie( 0 ); ios::sync_with_stdio( false ); ll n; cin>>n; irep(i,1,n){ ll a; cin>>a; G[a].push_back(i); // aは頂点iの親なので、a=>iに辺が張られる } dfs(0); cout<