题解：P10332 [UESTCPC 2024] 一站到底

· · 题解

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

四倍经验

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

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

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;
}