对每一个节点维护一个序列，初始即自己（长度为1），并记$a_{i}$和$b_{i}$分别为第$i$个点序列上0和1的个数（也需要存储具体的序列）
考虑$frac{b_{i}}{a_{i}}$最小中最深的非根节点（全局），其必然在其父亲之后选择，那么不妨将其与父亲合并，并将其的序列加入到父亲末尾（启发式合并）并利用$a_{i}$和$b_{i}$即可统计逆序对数量
（特别的，为了避免$a_{i}=0$，可以写成$frac{b_{i}}{a_{i}+b_{i}}$）
另外，合并需要两个并查集，分别维护深度最小的点以及位置，以及set去找到$frac{b_{i}}{a_{i}}$最小的点
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 set<pair<double,int> >s; 5 deque<int>v[N]; 6 int n,x,fa[N],f[N],pos[N],sum[N][2]; 7 long long ans; 8 int find(int k){ 9 if (k==f[k])return k; 10 return f[k]=find(f[k]); 11 } 12 double calc(int k){ 13 return 1.0*sum[k][1]/(sum[k][0]+sum[k][1]); 14 } 15 pair<double,int> get(int k){ 16 return make_pair(calc(pos[find(k)]),k); 17 } 18 void merge(int x,int y){ 19 x=find(x),y=find(y); 20 f[y]=x; 21 int xx=x; 22 x=pos[x],y=pos[y]; 23 deque<int>::iterator it; 24 if (v[x].size()<v[y].size()){ 25 while (!v[x].empty()){ 26 v[y].push_front(v[x].back()); 27 if (v[x].back())ans+=sum[y][0]; 28 v[x].pop_back(); 29 } 30 sum[y][0]+=sum[x][0]; 31 sum[y][1]+=sum[x][1]; 32 pos[xx]=y; 33 } 34 else{ 35 while (!v[y].empty()){ 36 v[x].push_back(v[y].front()); 37 if (!v[y].front())ans+=sum[x][1]; 38 v[y].pop_front(); 39 } 40 sum[x][0]+=sum[y][0]; 41 sum[x][1]+=sum[y][1]; 42 pos[xx]=x; 43 } 44 } 45 int main(){ 46 scanf("%d",&n); 47 for(int i=2;i<=n;i++)scanf("%d",&fa[i]); 48 for(int i=1;i<=n;i++)f[i]=pos[i]=i; 49 for(int i=1;i<=n;i++){ 50 scanf("%d",&x); 51 sum[i][x]++; 52 v[i].push_back(x); 53 if (i>1)s.insert(get(i)); 54 } 55 for(int i=1;i<n;i++){ 56 x=(*s.begin()).second; 57 set<pair<double,int> >::iterator it; 58 s.erase(s.begin()); 59 int y=find(fa[x]); 60 if (y!=1)s.erase(get(y)); 61 merge(fa[x],x); 62 if (y!=1)s.insert(get(y)); 63 } 64 printf("%lld",ans); 65 }