# 香料航线：题解

> 并列方案：三状态树 DP。Codex（GPT-6）采用的解法，程序见 [alternative.cpp](alternative.cpp)；与出题人解法的比较见[主题解](solution.zh.md)。


## 计算没有交易通路的概率

删去失效边后，每个连通分量都不能同时含低价节点和高价节点，否则就存在交易通路。先求满足这个条件的概率，再用 $1$ 减去它。

将树任选一点为根。对每个子树，要求内部已经分离出去的连通分量都合法，只记录与子树根相连的分量含哪些标记：

- 状态 $0$ ：两类都没有；
- 状态 $1$ ：只有低价节点；
- 状态 $2$ ：只有高价节点。

两类同时出现的状态 $3$ 直接丢弃。用 $dp_u[s]$ 表示子树满足上述条件、根分量状态为 $s$ 的概率。初始化只含节点 $u$ ：对应状态为一，其他为零。若节点同时属于两类，三个状态都为零。

## 合并一条边

设连接孩子 $v$ 的边失效概率为 $z$ .当前根状态为 $a$ ，孩子根状态为 $b$ .

边失效时，两分量分开，贡献

$$next[a]\mathrel{+}=dp_u[a]dp_v[b]z$$

边可用时，合并后状态是按位或 $a\mathbin{|}b$ .若结果不为 $3$ ，贡献

$$next[a\mathbin{|}b]\mathrel{+}=dp_u[a]dp_v[b](1-z)$$

每条边两种情况互斥且完备；不同孩子子树和连接边相互独立，故概率相乘。逐孩子合并即可。最终答案为

$$1-dp_{root}[0]-dp_{root}[1]-dp_{root}[2]$$

归纳可知，每个保留状态恰好累计内部所有分量合法的情形；根处理完后再没有外部连接，故补事件计算正确。这个算法不依赖高价节点至多两个的特殊结构，但仍使用题面原有范围。

## 模运算与复杂度

设模数为 $P=10^9+7$ ，输入分母最大值为 $U$ .预处理 $1$ 到 $U$ 的逆元：

$$inv[1]=1,\qquad inv[i]=-(P\mathbin{//}i)\,inv[P\bmod i]\pmod P$$

该式来自 $P=(P\mathbin{//}i)i+(P\bmod i)$ ；所有 $i<P$ ，所以逆元存在。用 $q_i inv[p_i]\bmod P$ 表示边失效概率，各次减法规范化到 $[0,P-1]$ .

每条边只合并固定数量的状态，时间和空间均为 $O(n+U)$ .使用显式父子遍历顺序，避免长链递归。重复列表编号只设置标记一次；任意列表为空时答案为零；两类节点重合时答案为一。

独立检查枚举小树每条边的保留或失效状态，直接用连通分量判断交易通路，并乘上每种状态的精确模概率。

## 程序与复现

本方案程序见 [alternative.cpp](alternative.cpp)。使用 C++17 编译后，可用 `tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径>` 生成输入和答案。固定种子与用例目的见 [生成计划](tests/plan.json)。性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。