香料航线题解¶

解法与取舍¶

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

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

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

没有高价点时答案为零。只有一个高价点时，把下面的主路径视为仅含它的单点即可。两个高价点时，取它们之间的唯一路径 \(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\) .

因此总失败概率为

\[ 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)\) .

各方案的五次重复计时与峰值内存记录见评测环境与性能。