对每一个节点维护一个序列，初始即自己（长度为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
2 using namespace std;
3 #define N 200005
4 set >s;
5 dequev[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 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::iterator it;
24 if (v[x].size()1)s.insert(get(i));
54 }
55 for(int i=1;i >::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 }