← 返回题目列表

Codeforces · 629/E

E. 家庭门和道路

中文机器翻译题面 查看原题

Famil Door的城市地图看起来像一棵树(无向连通无环图),所以其他人称之为Treeland。城市中有n个交叉路口,由n-1条双向道路连接。

家门有m位朋友住在城里。第i个朋友住在路口ui,工作在路口vi。城里的每个人都很不高兴,因为他们的家和工作地点之间只有一条简单的道路。

家族之门计划修建一条新路,他会从 n·(n - 1) / 2 种可能性中随机选择一条。请注意,他甚至可能在两个已经相连的城市之间修建一条新道路。

他知道,如果在Famil Door修建了一条新路之后,有一条从这个朋友家到工作地点再回来的路,并且不会两次走同一条路,那么他的每个朋友都会变得幸福。形式上,有一个包含 ui 和 vi 的简单循环。

此外,如果朋友变得快乐,他的快乐就等于这条路径的长度(很容易看出它是唯一的)。对于他的每个朋友 Famil Door 都想知道他的预期快乐,即如果我们只考虑存在这样一个循环的情况,那么包含 ui 和 vi 的循环的预期长度。

输入

输入的第一行包含整数 n 和 m (2 ≤ n, m ≤ 100 000) — Treeland 中的交叉点数量和 Famil Door 朋友的数量。

然后沿着描述双向道路的 n - 1 条线行驶。它们每个都包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n)——第 i 条道路连接的交叉口的索引。

输入的最后 m 行描述了 Famil Door 的朋友。这些行中的第 i 行包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 第 i 个朋友生活和工作的交叉点索引。

输出

对于每个朋友,如果他快乐,你应该打印快乐的期望值。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

4 3
2 4
4 1
3 2
3 1
2 3
4 1

输出 #1

4.00000000
3.00000000
3.00000000

输入 #2

3 3
1 2
1 3
1 2
1 3
2 3

输出 #2

2.50000000
2.50000000
3.00000000

注意

考虑第二个示例。

1. 道路 (1, 2) 和 (2, 3) 均有效,因此预期长度如果 $${ \frac { 2 + 3 } { 2 } } = 2. 5$$
2. 道路 (1, 3) 和 (2, 3) 让第二个朋友感到高兴。和朋友 1 一样,答案是 2.5
3.让第三个朋友开心的唯一方法是添加road(2, 3),所以答案是3