本题难度较大,需要一定的图论基础。没有了解过LCA和逆元的可以先去学习一下。
树上任意两个点的路径其实是唯一的,所以到达的概率需要通过数个可供选择的邻居数量的倒数相乘,设cnti是节点i的邻居数量,由于概率需要取模,所以我们应用快速幂求乘法逆元得到概率取模后的值。
这里简单介绍一下逆元的知识,假设x * y % mod == 1
,那么我们就称y是x的逆元,所以我们其实就是求类似于cnti的逆元。
首先考虑简单的情况,对于两个点u,v,如果它们在树上是祖先-子孙关系,那么通过dfs枚举到子孙v时,我们可以统计从根结点(这个可以自己定,这里我们定为0)到v这条路径上所有节点的1/(cnti−1)的累乘值:
比如对于1-2-3来说,这在树上是一条链,那么1记录的就是1/(cnt1−1),2记录的就是1/(cnt1−1)∗1/(cnt2−1),我们将这个值保存在path
中。
小美在树上迷路了,位于s节点,但他想去t节点。小美很精明,他每次都会选一条之前没有走过的路走,他想知道,他走到t的概率是多少?
包含多次询问,每次输出概率对109+7取余后的结果。可以证明x是唯一的。
如果最后答案为分数,则最简分式后的形式为ba,其中a,b互质。那么输出整数x使b∗x≡a(mod109+7)且0≤x<109+7。
第一行输入一个整数n(≤2∗105)表示树节点个数。
接下来n−1行,每行为u,v ,表示树上的边。
接下来一行,输入一个整数q(≤2∗105),代表询问次数。
接下来q行,每行为s,t表示询问。
输出q行,每行输出一个整数表示概率
输入
3
1 2
1 3
2
2 3
1 3
输出
1
500000004
说明
第一个询问,有1的概率从节点2走到节点1,然后有1的概率从节点1走到节点3。因此答案为1mod109+7=1
第二个询问,有1/2的概率从节点1走到节点2,有1/2的概率从节点1走到节点3。答案为1/2,按公式取余后结果为500000004