NOIp 前随机一道题来补。
NOIp2022 rp++
题意：
给定一棵树，每个点 \(p_i\) 概率被直接激活，每条边 \(p_{\{u,v\}}\) 概率被激活，被激活的点可以顺着被激活的边激活其它点，求所有点被激活的概率和。
\(n \leq 5 \cdot 10^5\)，保留小数输出。
这种树上题也只能是树形 dp 了，现在思考怎么计算这个贡献。
一个点能通过三种方式被激活：自己本身已被激活、通过子节点被激活、通过被激活的父节点被激活。
设一个点被激活的概率是 \(q_i\)，则它被直接激活的概率是 \(p_i\)，被子节点激活的概率容易通过递推算出，具体转移为 \(q_u \gets q_v \ (1-q’_u) \ p_{\{u,v\}}\)。
现在来看通过父节点被激活，那么首先要从父节点中去除 \(u\) 可能的贡献。
已知 \(q_{fa} = q’_{fa} + q_u \ (1-q’_{fa}) \ p_{\{u,v\}}\)，则可以解出 \(q’_{fa} = \dfrac{q_{fa}-q_u p_{\{u,v\}}}{1-q_u p_{\{u,v\}}}\)。这就是父节点被激活且不通过 \(u\) 的概率。用这个概率进行像上一个转移一样的转移即可。
拜谢 第二篇题解，思路讲得挺顺畅的，也给出了一个比第一篇题解好理解的去当前节点父节点概率的算法。
补完了。rp++;
其实感觉真不是特别难，最多概率的运算难一些，但是每一步都很自然。
学到了 up and down 的技巧，很开心！
是不是要说一下那句老话：
题出的好！难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞！
原文地址：http://www.cnblogs.com/purplevine/p/16923572.html
