AGC023F 01 on Tree 做题记录

给定一棵 $n$ 个点的有根树，每个节点上有一个 $0/1$ 权值。

你需要以这样的方式生成一个序列：

• 每次选择一个没有父节点（或者父节点已被删除）的点删除，将其上的权值放到序列的末尾；

请求出所有可能序列中逆序对数的最小值。

$1\le n\le 2\times 10^5$。

考虑这样刻画树的拓扑序：

• 每次找到相邻的两个（段）元素，将它们合并成一个（段）元素；

体现在树上就是每次找到一个连通块，将其与其根的父亲所在的连通块合并。

在本题中，考虑一个点（连通块）的两个儿子 $a,b$，设其中的 $0$ 和 $1$ 个数分别为 $c0_a,c1_a$ 和 $c0_b,c1_b$，则 $a$ 排在 $b$ 前面的代价为 $c1_a\times c0_b$，$b$ 排在 $a$ 前面的代价则为 $c1_b\times c0_a$，故 $a$ 排在前面更优当且仅当 $\frac{c1_a}{c0_a}$ 更小。

那么开一个优先队列，每次取出 $\frac{c1}{c0}$ 最小的连通块和其根的父亲所在的连通块合并即可。

这样做是对的基于一个结论：

考虑以任意一点 $u$ 为根的子树，其内部的点在全局最优方案中的顺序和子树内局部最优方案中的顺序相同。

具体证明可以归纳，不过理解起来很简单。

时间复杂度 $O(n\log n)$，代码如下：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int S=200005;

struct node
{
	int c0,c1,id;
	inline bool operator<(const node& y)const
	{
		if(1ll*c1*y.c0==1ll*y.c1*c0) return id>y.id;
		return 1ll*c1*y.c0>1ll*y.c1*c0;
	}
	inline bool operator==(const node& y)const
	{
		return c0==y.c0&&c1==y.c1&&id==y.id;
	}
};

int n,fat[S],a[S],c0[S],c1[S];
int fa[S];
priority_queue<node> q,deq;

int fnd(int x){return fa[x]==x?x:fa[x]=fnd(fa[x]);}

inline void push(node x){q.push(x);}
inline void del(node x){deq.push(x);}
inline bool empty(){return q.size()<=deq.size();}
inline node pop()
{
	while(!deq.empty()&&q.top()==deq.top()) q.pop(),deq.pop();
	node res=q.top();
	q.pop();
	return res;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++) cin>>fat[i];
	for(int i=1;i<=n;i++) cin>>a[i],c0[i]=(a[i]==0),c1[i]=(a[i]==1);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=2;i<=n;i++) push(node{c0[i],c1[i],i});
	ll ans=0;
	while(!empty())
	{
		node t=pop();
		int u=fnd(t.id),rt=fnd(fat[u]);
		if(rt!=1) del(node{c0[rt],c1[rt],rt});
		ans+=1ll*c1[rt]*c0[u];
		c0[rt]+=c0[u],c1[rt]+=c1[u];
		fa[u]=rt;
		if(rt!=1) push(node{c0[rt],c1[rt],rt});
	}
	cout<<ans<<'\n';
	return 0;
}