1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=400005,maxs=7000005,maxe=maxn;
int n,w[maxn],N,lson[maxn],rson[maxn];
void readin(int &x){
x=++N;
scanf("%d",&w[x]);
if (w[x]) return;
readin(lson[x]); readin(rson[x]);
}
int s[maxs],ls[maxs],rs[maxs],len,Rot[maxn];
void ist(int &x,int l,int r,int k){
if (!x) x=++len,s[x]=ls[x]=rs[x]=0;
if (l==r) {s[x]++;return;}
int mid=l+r>>1;
if (k<=mid) ist(ls[x],l,mid,k);else ist(rs[x],mid+1,r,k);
s[x]=s[ls[x]]+s[rs[x]];
}
ll ans=0,L,R;
int merge(int x,int y){
if (!x||!y) return x+y;
L+=(ll)s[ls[x]]*s[rs[y]];
R+=(ll)s[rs[x]]*s[ls[y]];
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
s[x]=s[ls[x]]+s[rs[x]];
return x;
}
void dfs(int x){
if (w[x]) ist(Rot[x],1,n,w[x]);
else{
dfs(lson[x]);dfs(rson[x]);
L=R=0;
Rot[x]=merge(Rot[lson[x]],Rot[rson[x]]);
ans+=min(L,R);
}
}
int main(){
scanf("%d",&n);
int x;readin(x);
dfs(1);
printf("%lld",ans);
return 0;
}
|
