香料航线：题解¶
并列方案：三状态树 DP。Codex（GPT-6）采用的解法，程序见 alternative.cpp；与出题人解法的比较见主题解。
计算没有交易通路的概率¶
删去失效边后，每个连通分量都不能同时含低价节点和高价节点，否则就存在交易通路。先求满足这个条件的概率，再用 \(1\) 减去它。
将树任选一点为根。对每个子树，要求内部已经分离出去的连通分量都合法，只记录与子树根相连的分量含哪些标记：
- 状态 \(0\) ：两类都没有；
- 状态 \(1\) ：只有低价节点；
- 状态 \(2\) ：只有高价节点。
两类同时出现的状态 \(3\) 直接丢弃。用 \(dp_u[s]\) 表示子树满足上述条件、根分量状态为 \(s\) 的概率。初始化只含节点 \(u\) ：对应状态为一，其他为零。若节点同时属于两类，三个状态都为零。
合并一条边¶
设连接孩子 \(v\) 的边失效概率为 \(z\) .当前根状态为 \(a\) ，孩子根状态为 \(b\) .
边失效时，两分量分开，贡献
边可用时，合并后状态是按位或 \(a\mathbin{|}b\) .若结果不为 \(3\) ，贡献
每条边两种情况互斥且完备；不同孩子子树和连接边相互独立，故概率相乘。逐孩子合并即可。最终答案为
归纳可知，每个保留状态恰好累计内部所有分量合法的情形；根处理完后再没有外部连接，故补事件计算正确。这个算法不依赖高价节点至多两个的特殊结构，但仍使用题面原有范围。
模运算与复杂度¶
设模数为 \(P=10^9+7\) ，输入分母最大值为 \(U\) .预处理 \(1\) 到 \(U\) 的逆元：
该式来自 \(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。使用 C++17 编译后，可用 tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径> 生成输入和答案。固定种子与用例目的见 生成计划。性能测量见 评测环境与性能。