随机爬树题解

随机爬树题解

题目传送门
更好的阅读体验
\(n^2\) 暴力：

思路：

• 求期望，即求所有点的权值乘上概率后的和，即：
  

\[ans=\sum_{u \in V}{P_u a_u}\]

• 求每个点的概率 \(P_u\) ：
  
  
  
  • 由题，令走到父亲的概率为 \(P_f\)，走到儿子 \(s\) 的概率则为 \(P_f \times \frac{w_s}{sum_f}\)（其中 \(sum_f\) 为 \(f\) 所有儿子的 \(w\) 之和）。
    
  
  
• 统计答案：
  
  
  
  • 记 \(ans_u\) 表示 \(u\) 子树（不含 \(u\) 本身）的答案之和，最终答案为 \(ans_1+a_1\)。
    
  • 暴力修改，跑 DFS 暴力求和即可。
    
  
  

代码：

[code]//n^2暴力 60pts#include#include#include#includeusing namespace std;typedef long long ll;const int N=1e5+5,Mod=998244353;int n,q,fa[N];ll sum[N],inv[N],w[N],a[N];ll p[N],ans[N];vector  e[N];ll qpow(ll a,ll b){    ll res=1;    while(b){        if(b&1) (res*=a)%=Mod;        (a*=a)%=Mod;        b>>=1;    }    return res%Mod;}void dfs(int u){    ans=0;    inv=qpow(sum,Mod-2);    for(int i=0;i

鼓励转贴优秀软件安全工具和文档！

感谢分享