CF629E Famil Door and Roads

Famil Door 的城市地图看起来像一棵树（无向连通无环图），因此其他人称之为“树之国”。城市中有 $n$ 个交叉路口，通过 $n-1$ 条双向道路连接。 Famil Door 有 $m$ 个朋友住在城里。第 $i$ 个朋友住在交叉路口 $u_i$，在交叉路口 $v_i$ 工作。市里所有人都不开心，因为他们家和工作之间只有唯一一条简单路径。 Famil Door 计划新建一条道路，他会在 $n·(n-1)/2$ 个可能的选择中随机挑选一对。注意，即使两座城市之间已经有一条道路，他也可以再建一条。 他知道，如果新建完道路后，这些朋友家到工作的路径和返回时不会经过同一条路（即存在一条包含 $u_i$ 和 $v_i$ 的简单环），这样朋友们才会开心。 此外，如果朋友变得开心，他的满足感等于该环的长度（显然这一定是唯一的）。Famil Door 想知道，对于每个朋友，他的期望满足感是多少，即在所有使他开心的情况下，包含 $u_i$ 和 $v_i$ 的环长度的期望值。

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n,\, m \leq 100000$），表示树之国的交叉路口数和 Famil Door 的朋友数。 接下来的 $n-1$ 行描述双向道路。每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i,\, b_i \leq n$），表示第 $i$ 条道路连接了 $a_i$ 和 $b_i$ 号交叉路口。 接下来的 $m$ 行描述 Famil Door 的朋友们。第 $i$ 行的两个整数 $u_i$、$v_i$（$1 \leq u_i,\, v_i \leq n,\, u_i \neq v_i$）表示第 $i$ 位朋友的家和工作的交叉路口编号。

对于每一个朋友，输出当他高兴时的期望满足感。如果答案的绝对误差或相对误差不超过 $10^{-6}$，就视为正确。 具体来说：假设你的答案为 $a$，标准答案为 $b$，当 $$ \frac{|a-b|}{\max(1, |b|)} \le 10^{-6} $$ 时，视为正确。

以第二个样例为例： 1. 道路 $(1,2)$ 和 $(2,3)$ 都可以使朋友开心，所以期望长度为 $\frac{2+3}{2}=2.5$。 2. 道路 $(1,3)$ 和 $(2,3)$ 可以使第二个朋友开心。同样得到 $2.5$。 3. 只有新建 $(2,3)$ 这条路能让第三位朋友开心，所以答案是 $3$。 由 ChatGPT 5 翻译