# 香料航线 题解

## 解法与取舍

**出题人解法：至多两个高价点的路径分类。** 路径分类利用题目中至多两个高价点的限制，作为标程。三状态树 DP 能直接处理更多高价点，作为适用范围更广的并列方案。两者均为 $O(n+U)$ 时间和空间，其中 $U$ 为输入最大分母。

**程序与署名：** [std.cpp](std.cpp) 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的三状态树 DP见 [alternative.cpp](alternative.cpp) 和[并列方案题解](solution-alternative.zh.md)。

## 先求没有交易通路的概率

交易成功等价于某个高价点与某个低价点连通。先求所有高价点都未连到低价点的概率，再取补集。

没有高价点时答案为零。只有一个高价点时，把下面的主路径视为仅含它的单点即可。两个高价点时，取它们之间的唯一路径 $x_0,\ldots,x_t$ .

## 压缩挂在主路径上的支树

对支树节点 $u$ ，令 $f_u$ 表示从 $u$ 无法经该支树到达任意低价点的概率。若 $u$ 是低价点，则 $f_u=0$ ；否则

$$f_u=\prod_{v\text{ 为支树孩子}}\bigl(q_{uv}+(1-q_{uv})f_v\bigr),$$

其中 $q_{uv}$ 为边断开的概率。每项分别对应边断开，或边接通但下面仍失败，两种事件互斥；不同支树独立。

对主路径上的每个点也计算相同的乘积，但排除沿主路径的孩子。所得 $f_i$ 就是主路径点不能通过自身或挂接支树连到低价点的概率，各 $f_i$ 使用的边彼此不交。

## 按第一条和最后一条断边分类

令主路径边 $(x_i,x_{i+1})$ 的断开概率为 $q_i$ .定义

$$A_i=\prod_{k=0}^{i}f_k\prod_{k=0}^{i-1}(1-q_k),\qquad
B_i=\prod_{k=i}^{t}f_k\prod_{k=i}^{t-1}(1-q_k).$$

主路径全通时，失败概率为 $B_0$ .如果路径有断边，设从左端遇到的第一条断边编号为 $i$ .

- 只有这一条断边：贡献 $A_iq_iB_{i+1}$ .
- 最后一条断边为 $j>i$ ：贡献 $A_iq_iq_jB_{j+1}$ .两条断边之间的状态任意，其总概率为一；那里没有高价点，不影响失败事件。

因此总失败概率为

$$B_0+\sum_{i=0}^{t-1}A_iq_i\left(B_{i+1}+\sum_{j=i+1}^{t-1}q_jB_{j+1}\right).$$

各类由唯一的第一、最后断边确定，互斥且完备。先算后缀 $B_i$ 和括号内的后缀和，再滚动维护 $A_i$ ，即可线性求值。主路径含低价点时，其 $f_i=0$ ，公式自然排除不合法事件，无须额外分类。高低价点重合也同样处理。

## 模运算与复杂度

对模数 $P=10^9+7$ ，输入分母均小于 $P$ ，预处理 $1$ 至 $U$ 的逆元，将断开概率写为分子乘分母逆元。只对输入分母求逆，不对 $f_i$ 或边接通概率求逆，因此零概率、必断边与必通边均可处理。

显式遍历收集主路径和后序，支树乘积、前后缀均为线性工作，总时间 $O(n+U)$ ，空间 $O(n+U)$ .

## 验证与性能

各方案的五次重复计时与峰值内存记录见[评测环境与性能](../../../docs/评测环境与性能.md)。