#C241114E. 树上宝藏
标签（Label）
- 概率期望
- 数学
- 贪心
网址（Website）
G - Treasure Hunting (atcoder.jp)
题目（Problem）
问题陈述
有一棵有根的树，树上有 $N + 1$ 个顶点，编号从 $0$ 到 $N$ 。顶点 $0$ 是根，顶点 $i$ 的父顶点是顶点 $p_i$ 。
顶点 $1$ 、顶点 $2$ 、…、顶点 $N$ 中的一个顶点藏有宝藏。宝藏位于顶点 $i$ 的概率是 $\frac{a_i}{\sum_{j=1}^N a_j}$ 。此外，每个顶点都处于两种状态之一：”搜索 “和 “未搜索 “两种状态之一。最初，顶点 $0$ 被搜索，其他所有顶点都未被搜索。
在包含宝藏的顶点被搜索到之前，执行以下操作：
- 选择一个父顶点已被搜索的未搜索顶点，并将其标记为已搜索。
求在最小化预期操作数的情况下所需的预期操作数，模为 $998244353$ 。
给你 $T$ 个测试案例，求解每个案例。
限制因素
- $1 \leq T \leq 2 \times 10^5$
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq p_i < i$
- $1 \leq a_i$
- $\sum_{i=1}^N a_i \leq 10^8$
- 所有测试用例中 $N$ 的总和最多为 $2 \times 10^5$ 。
- 所有输入值均为整数。
输入
输入信息按以下格式从 “标准输入”（Standard Input）中输入。这里， $\mathrm{case}_i$ 表示第 $i$ 测试用例。
$T\\
\mathrm{case}_1\\
\mathrm{case}_2\\
\vdots\\
\mathrm{case}_T\\$
每个测试用例的格式如下：
$N$
$p_1$ $p_2$ $\dots$ $p_N$
$a_1$ $a_2$ $\dots$ $a_N$
输出
打印 $T$ 行。第 $i$ 行应包含第 $i$ 测试用例的答案。
样例 #1
样例输入 #1
3
3
0 0 1
1 2 3
5
0 1 0 0 0
8 6 5 1 7
10
0 1 1 3 3 1 4 7 5 4
43 39 79 48 92 90 76 30 16 30样例输出 #1
166374061
295776107
680203339在第一个测试用例中，预期操作数为 $\frac{13}{6}$ 。
题解（Solution）
$\qquad$我们假设没有“子节点必须在父节点之后”的限制，那么这道题就变成了安排一种顺序使得最后得到宝藏的期望最小，很明显这个地方我们肯定先去选择有宝藏概率更大的点。
$\qquad$为了方便表示，我们记录 $p_i = \frac{a_i}{\sum_{i=1}^N a_i}$ （其实就是概率），那么最后的答案就是操作期望步数乘上发生概率即 $\sum_{i=1}^N i\times p_i$ ，那么现在就只需要考虑对于父亲的限制了，由于父亲只能先访问，我们试着推一下
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 1012345;
bool ST;
inline void add(int &x,int y){if((x+=y)>=mod) x-=mod;}
inline void mul(int &x,int y){x=x*y%mod;}
inline int inv(int x,int k=mod-2){
int res=1;while(k){
if(k&1) mul(res,x);
mul(x,x), k>>=1;
}return res;
}
int n,sm,ans,a[N],f[N];
int fa[N];inline int find(int x){
if(x==fa[x]) return x;
return fa[x] = find(fa[x]);
}
struct Wolf{
int val,siz,p,pos;
Wolf operator+(const auto y)const{
Wolf res;
res.val = (val+y.val+siz*y.p)%mod;
res.siz = siz+y.siz;
res.p = (p+y.p)%mod;
res.pos = pos;
return res;
}
bool operator<(const Wolf y)const{
return siz*y.p > y.siz*p;
}
}x[N];
priority_queue<Wolf> q;
bitset<N> vst;
void Solve(){
sm=ans=0;
cin>>n;For(x,1,n) f[x]=rd(), fa[x]=x;
For(i,1,n) a[i]=rd(),sm += a[i];
x[0] = {0,0,0,0};
For(i,1,n) x[i] = {a[i], 1, a[i], i};
For(i,1,n) q.emplace(x[i]), vst[i]=0;
while(q.size()){
auto w = q.top();q.pop();
if(vst[w.pos] || w.pos==0) continue;
vst[w.pos] = true;
int F = find(f[w.pos]);
fa[w.pos] = F;
x[F] = x[F] + x[w.pos];
q.emplace(x[F]);
}cout<<x[0].val*inv(sm)%mod<<'\n';
}
bool ED;
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
int Tt=rd();double Tim=clock();
while(Tt--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
