AT_abc376_G

题目大意

给定一棵树的形态，宝藏在每个点的概率是 a_i，每次可以探索一个已探索的点的子节点（初始时根已探索），问最优策略时找到宝藏的期望。

算法分析

我们需要知道的就是两个节点 x 和 y 的访问先后顺序，考虑如何计算：

首先我们容易得到，在没有限制的情况下肯定是先访问概率大的那一个，但是如果有限制的话，我们还要考虑它子树内的因素。

对于两个要访问的连通块 x 和 y，考虑 x 比 y 先访问（就是先合并到父亲所在的连通块）时一定满足：

这当中 val 表示访问完子树（扫完或找到宝藏）的期望，siz 表示字数大小，p 表示宝藏在这棵子树内的概率。这个式子的关键就是中间 x.siz\times y.p 的值，这个表示得先把 x 访问完（宝藏在 y 内）再访问 y 的贡献。

然后我们再用一个优先队列维护，同时用并查集记录祖先。

具体实现见代码。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=212345,mod=998244353;
int n,T,fa[N],f[N],a[N],sum;
bool tag[N];
struct Node{
    int val,siz,p,id;
}x[N];
bool operator<(Node x,Node y){
    return x.siz*y.p>y.siz*x.p;
}//大根堆条件是反的 
Node operator+(Node x,Node y){
    Node tmp;
    tmp.val=(x.val+x.siz*y.p+y.val)%mod;
    //合并和判断条件是一样的 
    tmp.siz=x.siz+y.siz;
    tmp.p=(x.p+y.p)%mod;
    tmp.id=x.id;
    return tmp;
}
priority_queue<Node>q;

int getfa(int x){
    if(x==f[x]) return x;
    return f[x]=getfa(f[x]);
}int qp(int w,int k) {
    int tmp=1;
    while(k){
        if(k&1) tmp=tmp*w%mod;
        w=w*w%mod;
        k>>=1;
    }
    return tmp;
}

void sol(){
    sum=0;
    x[0]={0,0,0,0};
    for(int i=1;i<=n;i++)
        tag[i]=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>fa[i];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        sum+=a[i];
        f[i]=i;//f记录祖先 
        x[i]={a[i],1,a[i],i};
        //把a[i]钦定为概率，sum放到最后计算答案再除 
        q.push(x[i]);
    }
    while(!q.empty()){
        Node u=q.top();q.pop();
        if(tag[u.id]||u.id==0) continue;
        //如果这个点已经合并了，或者是根
        tag[u.id] =1;
        int ff=getfa(fa[u.id]);
        f[u.id]=ff;
        //把它合并到它父亲所在的并查集中
        x[ff]=x[ff]+x[u.id];
        q.push(x[ff]);
        //合并信息 
    }
    cout<<x[0].val*qp(sum,mod-2)%mod<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--){
//      init();
        sol();
    }
    return 0;
}