【AGC023F】01 on Tree

题目

题目链接：https://atcoder.jp/contests/agc023/tasks/agc023_f

• 给出一棵 (n) 个节点的树，以及一个空序列。
• 每个节点上有一个取值在 ({0, 1}) 中的数。
• 每次你可以选择没有父亲节点的点删除，并且将这个节点上的数字放在当前数列末尾。
• 请你求出这个数列可能得到的最小逆序对数。
• (n leq 2 imes 10^5)

思路

等价于最终序列中任意一个点必须在其子树内所有点之前。
先考虑一个子问题：序列必须是树的一个 dfs 序。
假设我们已经定好 (x) 每棵子树内的顺序，记 (y) 子树内 (0/1) 的数量分别为 (a[y][0/1])。如果 (x) 的两个儿子 (y_1,y_2) 在序列中相邻，考虑交换他们，产生的逆序对数量为 (a[y_1][0] imes a[y_2][1])。
所以我们将点按照子树内 (frac{a[x][0]}{a[x][1}) 从小到大排序，然后贪心选取，每次选能选的在最前的一个即可。
考虑原问题，我们可以把每一个点先看作一个连通块，只有自己的数字，然后依然按照连通块的权值小到大排序。选择最小的标号后将他合并到其父亲所在连通块内，并更新父亲的权值。
显然这样贪心是最优的。最后在模拟一边选择过程计算即可。
时间复杂度 (O(nlog n))。

代码

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;

const int N=200010,Inf=1e9;
int n,tot,fa[N],father[N],id[N],b[N],a[N][2];
ll ans,cnt;
priority_queue<pair<double,int> > q,del;
priority_queue<pair<int,int> > q1;
vector<int> son[N];

int read()
{
	int d=0; char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) d=(d<<1)+(d<<3)+ch-48,ch=getchar();
	return d;
}

double calc(int x)
{
	if (!a[x][1]) return Inf;
	return 1.0*a[x][0]/a[x][1];
}

int find(int x)
{
	return x==father[x]?x:father[x]=find(father[x]);
}

int main()
{
	n=read();
	father[1]=1;
	for (int i=2;i<=n;i++)
	{
		fa[i]=read();
		son[fa[i]].push_back(i);
		father[i]=i;
	}
	for (int i=1;i<=n;i++)
	{
		b[i]=read(); a[i][b[i]]=1;
		if (i!=1) q.push(mp(calc(i),i));
	}
	id[1]=1023;
	for (int i=1;i<n;i++)
	{
		while ((del.size() && q.top()==del.top()) || id[q.top().second])
			q.pop(),del.pop();
		int x=q.top().second; q.pop();
		int y=find(fa[x]);
		del.push(mp(calc(y),y));
		a[y][0]+=a[x][0]; a[y][1]+=a[x][1];
		q.push(mp(calc(y),y));
		id[x]=i; father[x]=y;
	}
	q1.push(mp(19260817,1));
	for (int i=1;i<=n;i++)
	{
		int x=q1.top().second; q1.pop();
		if (!b[x]) ans+=cnt;
			else cnt++;
		for (int i=0;i<son[x].size();i++)
			q1.push(mp(-id[son[x][i]],son[x][i]));
	}
	printf("%lld
",ans);
	return 0;
}