#P18838. [Croatian CPC2020] Ekstremna Ekspedicija
[Croatian CPC2020] Ekstremna Ekspedicija
[Croatian CPC2020] Ekstremna Ekspedicija
题目描述
有一棵包含 个节点的无向树,节点编号为 至 ,每条边的通行时间均为一分钟。
Kile 计划进行 次旅行。第 次旅行从节点 开始,在第一次到达节点 时结束。
每当 Kile 位于某个节点时,他都会从与该节点相连的所有边中等概率随机选择一条,沿该边走到相邻节点;允许立即沿刚刚经过的边返回。
对于每次旅行,求它的期望持续时间。
为避免精度问题,将期望写成最简分数 ,你需要输出 ,其中 表示 在模 意义下的乘法逆元。
输入格式
第一行包含两个整数 (,)。
接下来 行,每行包含两个整数 (),表示一条无向边。保证这些边构成一棵树。
接下来 行,第 行包含两个不同的整数 (),表示第 次旅行的起点和终点。
输出格式
输出 行,第 行包含一个整数,表示第 次旅行的期望持续时间按上述方式取模后的结果。
样例 1
输入
5 3
1 2
1 3
2 4
2 5
3 5
1 5
2 4
输出
11
10
7
样例 2
输入
3 1
1 2
2 3
2 3
输出
3
样例 2 说明
从节点 出发,有一半概率用一步到达节点 ,另一半概率先到节点 ,再用一步回到节点 重新开始。最终期望时间为 。