← 返回题目列表

Codeforces · 1085/D

D. 最小直径树

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

给你一棵树(没有循环的无向连通图)和一个整数 $$$s$$$。

Vanya 希望将权重放在树的所有边上,以便所有权重都是非负实数,并且它们的总和为 $$$s$$$。同时,他想让树的直径尽可能小。

让我们将加权树的直径定义为位于树的两个顶点之间的路径上的边的权重的最大总和。换句话说,加权树的直径是树中最长的简单路径的长度,其中路径的长度等于路径中所有边的权重之和。

求 Vanya 可以获得的最小可能直径。

输入

第一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq s \leq 10^9$$$) — 树中的顶点数和边权重之和。

以下 $$$n−1$$$ 行中的每一行都包含两个以空格分隔的整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — 由边连接的顶点的索引。边缘是无向的。

保证给定的边形成一棵树。

输出

打印 Vanya 通过在其边缘放置一些非负实数权重而获得的树的最小直径,其总和等于 $$$s$$$。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。如果 $$$\frac {|a-b|} {max(1, b)} \leq 10^{-6}$$$,则认为您的答案是正确的。

示例

输入 #1

4 3
1 2
1 3
1 4

输出 #1

2.000000000000000000

输入 #2

6 1
2 1
2 3
2 5
5 4
5 6

输出 #2

0.500000000000000000

输入 #3

5 5
1 2
2 3
3 4
3 5

输出 #3

3.333333333333333333

注意

在第一个示例中,需要像这样放置权重:

很容易看出这棵树的直径是$$$2$$$。可以证明它是可能的最小直径。

在第二个示例中,需要像这样放置权重: