D2T2

· · 题解

本题解为官方题解。

树

设 f[u] 为节点 u 有水流时子树 u 中有流水的节点数量的期望。

设 $g[u]$ 为节点 $u$ 的答案，则可以进行换根 DP 计算出 $g$。 $g[v]=f[v]+p_{(u,v)}(g[u]-p_{(u,v)}f[v])

总时间复杂度为 O(n+q)。

暴力

### 基环树 设 $f[u]$ 为环上的节点 $u$ 如果有水流下挂的子树中有水的期望节点数，这部分可以使用 Tree 部分的 DP 求得。 令环上所有边的概率乘积为 $P$，即 $P=\prod_{j\in C} p_j$，则 $g_i=\sum_{i,j\in C} (w(i,j)+\dfrac{P}{w(i,j)}-P)f_j$，其中 $w(i,j)$ 为环上节点 $i,j$ 任意一个方向上之间的边的概率之积。 对于该部分，断环成链后对边做前缀积，有 $s_i=\prod_{j\le i} p_j$。 对 $i\geq j$ 和 $i<j$ 分开讨论，得到 $g_i=s_i\sum_{j\le i}\dfrac{f_j}{s_j}+\dfrac{P}{s_i}\sum_{j\le i}f_js_j-P\sum_{j\le i}f_j+\dfrac{1}{s_i}\sum_{j>i}f_js_j+Ps_i\sum_{j>i}\dfrac{f_j}{s_j}-P\sum_{j>i}f_j

正序循环处理 j\le i 的 \sum，倒序循环处理 j>i 的 \sum。即可求出环上每个点的 g_u，然后从环上向下做类似换根 DP 即可得到所有点的 g。

由于求出 g 的部分需要求出前缀积 s_i 的逆元，时间复杂度为 O(n\log \operatorname{mod}+m)。

点仙人掌

考虑这个图的 dfs 树，由于是点仙人掌，所以每个点只可能在一个简单环中，无向图的 dfs 树形如一棵树与若干条返祖边的组合，我们可以借鉴前述的 Tree 和 Pseudotree 两个部分的算法。

首先选择一个节点作为 dfs 树的树根进行 dfs，对于每个节点计算 f[u]，表示当该节点有水的时候在不走环边的情况下其 dfs 树子树中期望会有多少个节点有水，由于是点仙人掌，每个点、边均只会属于至多一个环。对于某个环的最顶部节点要特殊处理，环顶部节点的 f[u] 应该为 u 到该 dfs 树子树中的期望联通点数。

计算完成后可以得到根节点的 g，然后类似换根 DP 往下做，对于节点 u - 非环节点 v，转移方式与树型的转移相同，当一个环的顶部节点得到 u 之后就可以使用基环树的方法算出环上所有点的答案。

于是成功的预处理了所有点的答案。

标准解法

对于非环中的节点，f[u] 代表若节点 u 有水流，在其 dfs 树的子树中期望会有多少个点也会有水流，状态转移方程：

g[u]=f[u]=\sum_{v\in son_u} p_{(u,v)}f[v]

对于环中的节点，则 f[u] 代表若节点 u 有水流，在不经过环上的边的情况下其 dfs 树的子树中期望会有多少个点也会有水流，状态转移方程：

g[u]=f[u]=\sum_{v\in son_u,(u,v)\notin C}p_{(u,v)}f[v]

若该节点为环的顶部节点，则 f[u] 代表若节点 u 有水流，在其 dfs 树的子树中期望会有多少个点也会有水流，此时对于这个环上只考虑子树内的节点的情况下，将其视为一个基环树，根据基环树部分分的计算方法重新计算出 f[u] ，有：

f[u]=\sum_{v\in C} (w(u,v)+\dfrac{P}{w(u,v)}-P)f[v] P=\prod_{(x,y)\in C} p_{(x,y)}

综上可以计算出每个节点的 f[u]。

对于前述的计算每个节点的 f[u] 方法中，如果开始 dfs 的节点为 root，那么 ans[root]=f[root]，对于其余节点，我们将使用类似换根 DP 的方法自上而下计算 ans[u]。

考虑从当前节点 u 向 dfs 树上子节点 v 进行推算。

我们只考虑 u,v 不在同一个环中的情况。

容易发现此时 v 一定是环的顶部节点，计算 ans[v] 其实就是考虑 (u,v) 这条边会给节点 v 带来的改变，容易发现，f[v] 只考虑了 dfs 树中 v 下方的部分，我们将 v 从 ans[u] 中去掉即可得到一个类似子树的部分的贡献，将其加到 f[v] 中即可得到 ans[v]，即：

ans[v]=f[v]+p_{(u,v)}(ans[u]-f[v]\times p_{(u,v)})

同时，当一个环的顶部节点的 ans[] 确定之后，其实我们就可以算出环上每个点的 ans[]，参考基环树部分，我们需要的就是得到环上每个节点下挂的一个子树对于环上的对应子树根节点的贡献，但是在 Part1 中我们因为无法确认环的顶部节点的这部分值不能立即确定，但是现在可以确定了，对于顶部节点，我们考虑其 dfs 树父亲的那条边带来的额外贡献后就可以算出这个环上的全部 ans[] 了，方法和基环树部分分一样。

然后发现，当 u,v 在同一个环中时，ans[] 一定都计算完毕了。

综上计算出了每个点的 ans[]，可以 O(1) 回答询问。

总时间复杂度 O((n+m)\log \text{mod}+Q)。