香料航线¶
- 参考时间限制：0.5 秒（评测环境与性能）。
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB
背景故事¶
香料商人的贸易网络连接着许多星球，部分星球低价出售香料，另一些星球高价收购。航线可能遭到静态干扰，使载货飞船无法通行。商人想知道，干扰发生后，是否还至少有一对买卖地点能通过完整航线互通。
形式化问题描述¶
给定一棵 \(n\) 个节点的无向树。第 \(i\) 条边以概率 \(q_i/p_i\) 失效，各边失效事件相互独立。失效边不能通行，其他边可以双向通行。
给定低价节点列表和高价节点列表。列表内以及两列表之间都允许重复；重复列出一个节点不增加新的条件。如果某节点同时属于两类，长度为零的路径也算连通。
求至少存在一个低价节点和一个高价节点，在删除全部失效边后仍然连通的概率。答案表示为最简分数 \(x/y\) 时，输出 \(x\cdot y^{-1}\bmod P\) ，其中 \(P=10^9+7\) ，\(y^{-1}\) 是模 \(P\) 的乘法逆元。
输入格式¶
第一行一个整数 \(n\) .接下来 \(n-1\) 行，每行四个整数 \(u,v,q_i,p_i\) ，表示边及其失效概率。然后一行整数 \(a\) ，下一行 \(a\) 个低价节点编号；再一行整数 \(b\) ，下一行 \(b\) 个高价节点编号。列表为空时，对应编号行为空。
输出格式¶
输出一个整数，表示上述概率对 \(P\) 取模的结果。
样例 1¶
输入¶
5
1 2 0 1
2 3 0 1
2 4 1 2
2 5 1 2
2
4 5
2
1 3
输出¶
750000006
样例 2¶
输入¶
3
1 2 1 2
2 3 1 3
2
1 3
1
2
输出¶
833333340
样例 3¶
输入¶
1
1
1
2
1 1
输出¶
1
样例解释¶
样例 1 中，节点 \(1,2,3\) 始终连通，只要通向节点 \(4\) 或 \(5\) 的两条边至少一条可用即可，概率为 \(1-(1/2)^2=3/4\) .样例 2 的概率为 \(1-(1/2)(1/3)=5/6\) .样例 3 中唯一节点同时属于两类，概率为 \(1\) .
L 标记低价节点，H 标记高价节点；边上标注失效概率。
数据范围与保证¶
所有数据满足 \(1\le n\le100000\) ，\(0\le a\le n\) ，\(0\le b\le2\) ，\(0\le q_i\le p_i\le100000\) ，\(p_i\ge1\) .所有节点编号在 \([1,n]\) 内，输入边构成一棵树。由于分母都小于素数 \(P\) ，答案所需逆元存在。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |