E. LeaFall 详细题解

一、问题理解

有一棵 $n$ 个节点的树。每个节点 $i$ 以概率 $pr_i = \frac{p_i}{q_i}$ 独立倒下（移除自身和邻边），剩余节点形成森林。需要计算期望的叶子对数量（无序，叶子定义为度数为 $1$ 的节点），结果对 $998244353$ 取模。

---

二、核心公式

设随机变量 $X$ = 叶子对数量。由期望线性性：

$$E[X] = \sum_{1 \le u < v \le n} P(\text{节点 } u \text{ 和 } v \text{ 都是叶子}) $$

标程的核心思想：

1. 先假设所有顶点对独立，计算近似期望
2. 再对距离 $\le 2$ 的顶点对进行修正（因为只有这些顶点的事件会相互依赖）

---

三、符号定义

• $pr_i = \frac{p_i}{q_i}$ 表示节点 $i$ 倒下的概率
• $qr_i = 1 - pr_i$ 表示节点 $i$ 未倒下的概率
• $fall[i] = pr_i$
• $stay[i] = 1 - pr_i$

---

四、单个节点成为叶子的概率 $p2[i]$

节点 $i$ 成为叶子，当且仅当：

• $i$ 未倒下
• $i$ 的邻居中恰好有一个未倒下，其余全部倒下

设 $N(i)$ 为 $i$ 的邻居集合。

先计算 $p1[i]$：$i$ 未倒下且所有邻居都倒下的概率：

$$p1[i] = stay[i] \cdot \prod_{u \in N(i)} pr_u$$

然后，$i$ 成为叶子的概率 = 对每个邻居 $u$，让 $u$ 成为那个唯一未倒下的邻居：

$$p2[i] = \sum_{u \in N(i)} \left( stay[i] \cdot (1-pr_u) \cdot \prod_{\substack{w \in N(i) \\ w \ne u}} pr_w \right) $$

注意到：

$$stay[i] \cdot \prod_{\substack{w \in N(i) \\ w \ne u}} pr_w = \frac{p1[i]}{pr_u} $$

所以：

$$p2[i] = \sum_{u \in N(i)} \frac{p1[i]}{pr_u} \cdot (1-pr_u) = p1[i] \cdot \sum_{u \in N(i)} \frac{1-pr_u}{pr_u} $$

标程中的计算正是这个公式：

p1[i] = sub(1, p[i]);
for (int u : adj[i]) p1[i] = mul(p1[i], p[u]);

for (int u : adj[i]) {
    int term = mul(p1[i], mul(inv(p[u]), sub(1, p[u])));
    add2(p2[i], term);
}

---

五、初始期望（假设独立）

如果所有顶点对独立，则：

$$E_{\text{indep}} = \sum_{u<v} p2[u] \cdot p2[v] = \frac{1}{2}\left( \left(\sum p2[i]\right)^2 - \sum p2[i]^2 \right) $$

标程第一段循环实现了这个：

int ans = 0, sum = 0;
for (int i = 1; i <= n; i++) {
    add2(ans, mul(p2[i], sum));
    add2(sum, p2[i]);
}

这里 ans 累积的是 $\sum_{j< i} p2[j] \cdot p2[i]$，即 $\sum_{u<v} p2[u] \cdot p2[v]$。

---

六、修正距离为 $1$ 的顶点对（相邻节点）

对于相邻节点 $(u,v)$，事件“$u$ 是叶子”和“$v$ 是叶子”不独立，需要重新计算联合概率并替换独立近似。

联合概率：$u$ 和 $v$ 都是叶子

条件：

• $u$ 未倒下，$v$ 未倒下
• $u$ 的邻居中恰好一个未倒下（这个未倒下的邻居必须是 $v$，否则 $u$ 会有其他未倒下邻居）
• $v$ 的邻居中恰好一个未倒下（这个未倒下的邻居必须是 $u$）
• 其他所有邻居（除了 $u$ 和 $v$ 彼此）必须全部倒下

设 $N(u)$ 为 $u$ 的邻居集合，$N(v)$ 为 $v$ 的邻居集合。

则联合概率为：

$$\begin{aligned} P(\text{leaf}_u \land \text{leaf}_v) &= stay[u] \cdot stay[v] \cdot (1-pr_v) \cdot (1-pr_u) \\ &\quad \cdot \prod_{w \in N(u) \setminus \{v\}} pr_w \cdot \prod_{w \in N(v) \setminus \{u\}} pr_w \end{aligned} $$

注意 $stay[u] \cdot \prod_{w \in N(u) \setminus \{v\}} pr_w = \frac{p1[u]}{pr_v}$。

所以：

$$P(\text{leaf}_u \land \text{leaf}_v) = \frac{p1[u]}{pr_v} \cdot \frac{p1[v]}{pr_u} \cdot (1-pr_u)(1-pr_v) $$

标程中：

int pi = mul(p1[i], inv(p[u]));   // = p1[i] / p[u]
int pu = mul(p1[u], inv(p[i]));   // = p1[u] / p[i]
add2(ans, mul(pi, pu));           // 加上精确联合概率
sub2(ans, mul(p2[i], p2[u]));     // 减去之前独立的贡献

---

七、修正距离为 $2$ 的顶点对（经过中间节点 $i$）

设 $u$ 和 $v$ 是 $i$ 的两个不同邻居，即 $i$ 是 $u$ 和 $v$ 的公共邻居。需要计算 $P(\text{leaf}_u \land \text{leaf}_v)$。

情况分析：$u$ 和 $v$ 成为叶子的条件涉及 $i$ 的状态。

标程将 $i$ 是否倒下分开处理：

情况 1：$i$ 未倒下

则 $u$ 成为叶子的条件：

• $u$ 未倒下
• $u$ 的邻居中恰好一个未倒下，且这个邻居必须是 $i$（因为 $i$ 未倒下，$u$ 的其他邻居必须全部倒下）

所以 $u$ 成为叶子的概率（给定 $i$ 未倒下）为：

$$\frac{p1[u]}{pr_i} \cdot (1-pr_i)$$

因为 $p1[u] = stay[u] \cdot \prod_{w \in N(u)} pr_w$，除以 $pr_i$ 去掉 $i$ 的因子，再乘以 $stay[i] = 1-pr_i$ 是因为 $i$ 未倒下。

标程中：

int pu = mul(p1[u], inv(p[i]));   // = p1[u] / p[i]
add2(ans, mul(sum, pu));
add2(sum, mul(pu, sub(1, p[i])));

情况 2：$i$ 倒下

则 $u$ 成为叶子的条件：

• $u$ 未倒下
• $u$ 的邻居中恰好一个未倒下，且这个邻居不能是 $i$（因为 $i$ 已倒下），所以必须是 $u$ 的其他某个邻居

计算 $u$ 成为叶子且 $i$ 倒下的概率 = $p2[u] - P(\text{leaf}_u \land i \text{ 未倒下})$。

其中 $P(\text{leaf}_u \land i \text{ 未倒下}) = \frac{p1[u]}{pr_i} \cdot (1-pr_i)$。

标程中：

int pu = sub(p2[u], mul(p1[u], mul(inv(p[i]), sub(1, p[i]))));
add2(ans, mul(sum, pu));
add2(sum, mul(pu, inv(p[i])));

---

八、算法流程总结

1. 读入 $n$、每个节点的 $(p_i, q_i)$、树的边
2. 计算 $pr_i = p_i \cdot q_i^{-1} \bmod M$
3. 计算 $p1[i]$：节点 $i$ 未倒下且所有邻居倒下的概率
4. 计算 $p2[i]$：节点 $i$ 成为叶子的概率
5. 初始化 ans 为所有无序对的独立贡献 $\sum_{u<v} p2[u] \cdot p2[v]$
6. 对每条边 $(u,v)$（距离 $1$）：
   • 加上精确联合概率
   • 减去独立贡献
7. 对每个节点 $i$，处理以 $i$ 为中间节点的距离 $2$ 的顶点对：
   • $i$ 未倒下时的情况
   • $i$ 倒下时的情况
8. 输出 ans

---

九、复杂度分析

• 预处理 $p1, p2$：$O(\sum deg) = O(n)$
• 初始贡献：$O(n)$
• 距离 $1$ 修正：$O(n)$（每条边一次）
• 距离 $2$ 修正：$O(\sum deg^2)$，最坏情况星形树可能 $O(n^2)$，但由于 $\sum deg^2$ 在稀疏图中通常可控，且 $n \le 10^5$ 时仍可接受

---

十、示例验证

以题目第二个测试用例为例：

• $n=3$，树为 $1-2-3$，所有 $pr_i = \frac{1}{2}$
• 计算得 $p2[1]=p2[3]=\frac{1}{4}$，$p2[2]=\frac{1}{2}$
• 初始独立贡献：$p2[1]p2[2] + p2[1]p2[3] + p2[2]p2[3] = \frac{1}{8} + \frac{1}{16} + \frac{1}{8} = \frac{5}{16}$
• 修正后得到 $\frac{3}{8}$，与题目一致

---

十一、总结

要点	说明
核心思想	线性期望 + 独立近似 + 局部修正
关键公式	$p2[i] = p1[i] \sum_{u \in N(i)} \frac{1-pr_u}{pr_u}$
修正范围	只修正距离 $\le 2$ 的顶点对
时间复杂度	$O(\sum deg^2)$，实际可过
模运算	使用模逆处理分数