BZOJ题目传送门 洛谷题目传送门
学了发线段树合并。
对于一棵子树，无论它是否交换，都不会影响到这棵子树外的其它节点。那么我们只要每一次取小的那个就好了。
对每个节点开一棵权值线段树，每次把左右儿子合并上来。而左右儿子有两个贡献，分别为一个儿子左区间的数个数*另一个儿子右区间的数个数，对这两个取min即可。
代码：
#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define N 400005 #define F inline using namespace std; typedef long long LL; struct tree{ int l,r; LL s; }t[N<<4]; int n,m,nd,a[N],to[N][2],rt[N]; LL ans,L,R; F char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); return l==r?EOF:*l++; } F int _read(){ int x=0; char ch=readc(); while (!isdigit(ch)) ch=readc(); while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc(); return x; } void dfs1(int &x){ if (!(a[x=++nd]=_read())) dfs1(to[x][0]),dfs1(to[x][1]); } F void pshp(int x){ t[x].s=t[t[x].l].s+t[t[x].r].s; } void mdfy(int &x,int l,int r,int p){ x=++nd; int mid=l+r>>1; if (l==r) return void(t[x].s=1); if (p<=mid) mdfy(t[x].l,l,mid,p); else mdfy(t[x].r,mid+1,r,p); pshp(x); } int mrg(int x,int y){ if (!x||!y) return x+y; L+=t[t[x].r].s*t[t[y].l].s; R+=t[t[x].l].s*t[t[y].r].s; t[x].l=mrg(t[x].l,t[y].l); t[x].r=mrg(t[x].r,t[y].r); return pshp(x),x; } LL dfs(int x){ LL ret=0; if (!a[x]){ ret=dfs(to[x][0])+dfs(to[x][1]),L=R=0; rt[x]=mrg(rt[to[x][0]],rt[to[x][1]]),ret+=min(L,R); } else mdfy(rt[x],1,n,a[x]); return ret; } int main(){ return n=_read(),dfs1(m),nd=0,printf("%lld\n",dfs(1)),0; }