//yuki778.cpp //Mon Jan 13 11:11:32 2020 #include #include #include #include #include #include #include #include #include #define INTINF 2147483647 #define LLINF 9223372036854775807 using namespace std; using ll=long long; typedef pair P; vector graph[200010]; vector tour; int l[200010]; int r[200010]; int bit[500010]; void add(int x, int y){ while(x<=tour.size()+1){ bit[x] += y; x += x & -x; } } int sum(int i){ int ans = 0; while (i>0){ ans += bit[i]; i -= i & -i; } return ans; } void dfs(int x){ tour.push_back(x); if (l[x]==-1){ l[x]=tour.size()-1; }else{ r[x]=tour.size()-1; } for (int i=0;i> n; for (int i=1;i> temp; graph[temp].push_back(i); } fill(l,l+200010,-1); fill(r,r+200010,-1); dfs(0); fill(bit,bit+tour.size()+1,0); int ans = 0; for (int i=n-1;i>=0;i--){ if (r[i]!=-1){ ans += sum(r[i]+1)-sum(l[i]); } add(l[i]+1,1); } // for (int i=0;i