随机爬树题解
随机爬树题解题目传送门
更好的阅读体验
\(n^2\) 暴力：
思路：
[*]求期望，即求所有点的权值乘上概率后的和，即：
\
[*]求每个点的概率 \(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 暴力求和即可。
代码：
//n^2暴力 60pts#include#include#include#includeusing namespace std;typedef long long ll;const int N=1e5+5,Mod=998244353;int n,q,fa;ll sum,inv,w,a;ll p,ans;vectore;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 鼓励转贴优秀软件安全工具和文档！ 感谢分享 收藏一下 不知道什么时候能用到
页:
[1]