自动搬运

查看原文

来自洛谷，原作者为

	OldDriverTree 人間になりたい

搬运于2025-08-24 22:57:00，当前版本为作者最后更新于2024-06-02 22:47:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

套路题，学过这题的套路随便推一下就能切出来。

四倍经验

虽然不同，但是套路相同，学过套路能秒出来。

做完这四道题能对这个套路有更好的理解。

• P10332 [UESTCPC 2024] 一站到底
• AT_agc023_f [AGC023F] 01 on Tree
• UVA1205 Color a Tree
• P4437 [HNOI/AHOI2018] 排列

Solution

先考虑假如知道了两个连通块 $a$ 和 $b$ 内部的答题顺序，先答哪个连通块最优。

令 $a_p$ 为答完 $a$ 的概率，$a_{ans}$ 为答连通块 $a$ 的期望得分，$b_p$ 和 $b_{ans}$ 同理。

先答 $a$ 再答 $b$ 的期望得分为 $a_{ans}+a_pb_{ans}$。

先答 $b$ 再答 $a$ 的期望得分为 $b_{ans}+b_pa_{ans}$。

先答 $a$ 更优当且仅当 $a_{ans}+a_pb_{ans}>b_{ans}+b_pa_{ans}$，经过移项得 $\dfrac{a_p-1}{a_{ans}}>\dfrac{b_p-1}{b_{ans}}$。

考虑用堆维护每个连通块，一开始每个点为一个连通块，堆顶为 $\dfrac{p-1}{ans}$ 最大的。

每次把堆顶取出来，并把堆顶所在的连通块和堆顶的父亲所在的连通块合并起来，合并后的 $p$ 和 $ans$ 不难维护，最后的答案就为合并到只剩一个连通块时这个连通块的 $ans$，时间复杂度为 $O(n\log n)$。

Code

//when you use vector or deque,pay attention to the size of it.
//by OldDirverTree
#include<bits/stdc++.h>
#define P pair<double,int>
#define int long long
#define mid (l+r>>1)
using namespace std;
const int N=1e5+1;
int n,a[N],Fa[N],fa[N];
priority_queue<P> q;
double p[N],ans[N];
bool st[N];

int read() {
	int x=0; bool f=true; char c=0;
	while (!isdigit(c) ) f&=(c!='-'),c=getchar();
	while (isdigit(c) ) x=(x<<3)+(x<<1)+(c&15),c=getchar();
	return f?x:-x;
}
int find(int x) {
	return fa[x]^x?fa[x]=find(fa[x]):x;
}
main()
{
	n=read();
	for (int i=1;i<=n;i++) a[i]=read(),fa[i]=i;
	for (int i=1;i<=n;i++) scanf("%lf",&p[i]),ans[i]=p[i]*a[i];
	for (int i=2;i<=n;i++) Fa[i]=read(),q.push({(p[i]-1)/ans[i],i});
	while (!q.empty() )
	{
		int u=q.top().second; q.pop();
		if (st[u]) continue; st[u]=true; int x=find(Fa[u]);
		fa[u]=x,ans[x]+=p[x]*ans[u],p[x]*=p[u];
		if (x^1) q.push({(p[x]-1)/ans[x],x});
	}
	printf("%.9lf",ans[1]);
	return 0;
}