题目描述

小美在树上迷路了，位于$s$节点，但他想去$t$节点。小美很精明，他每次都会选一条之前没有走过的路走，他想知道，他走到$t$的概率是多少？

包含多次询问，每次输出概率对$10^9+7$取余后的结果。可以证明$x$是唯一的。

题目思路

本题难度较大，需要一定的图论基础。没有了解过LCA和逆元的可以先去学习一下。

树上任意两个点的路径其实是唯一的，所以到达的概率需要通过数个可供选择的邻居数量的倒数相乘，设$cnt_i$是节点$i$的邻居数量，由于概率需要取模，所以我们应用快速幂求乘法逆元得到概率取模后的值。

这里简单介绍一下逆元的知识，假设x * y % mod == 1，那么我们就称y是x的逆元，所以我们其实就是求类似于$cnt_i$的逆元。

首先考虑简单的情况，对于两个点$u,v$，如果它们在树上是祖先-子孙关系，那么通过dfs枚举到子孙v时，我们可以统计从根结点（这个可以自己定，这里我们定为0）到v这条路径上所有节点的$1/(cnt_i-1)$的累乘值： 比如对于1-2-3来说，这在树上是一条链，那么1记录的就是$1/(cnt_1-1)$，2记录的就是$1/(cnt_1-1) * 1/(cnt_2-1)$，我们将这个值保存在path中。