Minimum Diameter Tree
Contest: Technocup 2019 - Elimination Round 4
Difficulty rating: 1700
Tags: constructive algorithms, implementation, trees

You are given a tree (an undirected connected graph without cycles) and an integer $$$s$$$.

Vanya wants to put weights on all edges of the tree so that all weights are non-negative real numbers and their sum is $$$s$$$. At the same time, he wants to make the diameter of the tree as small as possible.

Let's define the diameter of a weighed tree as the maximum sum of the weights of the edges lying on the path between two some vertices of the tree. In other words, the diameter of a weighed tree is the length of the longest simple path in the tree, where length of a path is equal to the sum of weights over all edges in the path.

Find the minimum possible diameter that Vanya can get.

Input format:
The first line contains two integer numbers $$$n$$$ and $$$s$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq s \leq 10^9$$$) — the number of vertices in the tree and the sum of edge weights.

Each of the following $$$n−1$$$ lines contains two space-separated integer numbers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — the indexes of vertices connected by an edge. The edges are undirected.

It is guaranteed that the given edges form a tree.

Output format:
Print the minimum diameter of the tree that Vanya can get by placing some non-negative real weights on its edges with the sum equal to $$$s$$$.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is considered correct if $$$\frac {|a-b|} {max(1, b)} \leq 10^{-6}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example it is necessary to put weights like this:

It is easy to see that the diameter of this tree is $$$2$$$. It can be proved that it is the minimum possible diameter.

In the second example it is necessary to put weights like this:

Example input:
4 3
1 2
1 3
1 4

Example output:
2.000000000000000000

Example input:
6 1
2 1
2 3
2 5
5 4
5 6

Example output:
0.500000000000000000

Editorial:
Let's denote the number of leaves in this tree for $$$l$$$.
Let's prove that the answer is $$$\frac {2s} {l}$$$.
To construct an example with such diameter, let's put the weight $$$\frac s l$$$ to the edge adjacent to the leaf, and let's put the weight $$$0$$$ to other edges. It is easy to see that the diameter of this tree is $$$\frac {2s} {l}$$$.
To prove that it is the minimal possible diameter we denote leaf numbers for $$$a_1, \ldots, a_l$$$. For $$$dist_{{x}{y}}$$$ we denote the sum of weights of edges lying on the path between vertices $$$x$$$ and $$$y$$$. Then $$$\frac {l(l-1)} 2 \cdot \max\limits_{1 \leq i < j \leq l}dist_{{a_i}{a_j}} \geq \sum\limits_{1 \leq i < j \leq l}dist_{{a_i}{a_j}}$$$. Note that the contribution to the sum on the right side of the inequality of the weight of each edge will be at least $$$l-1$$$, because any edge lies on $$$\geq l-1$$$ paths between the leaves of the tree. So, $$$\sum\limits_{1 \leq i < j \leq l}dist_{{a_i}{a_j}} \geq (l-1) \cdot \sum\limits_{e \in E} weight_e = (l-1) \cdot s$$$. So, $$$\frac {l(l-1)} 2 \cdot \max\limits_{1 \leq i < j \leq l}dist_{{a_i}{a_j}} \geq (l-1) \cdot s$$$ and we get that $$$\max\limits_{1 \leq i < j \leq l}dist_{{a_i}{a_j}} \geq \frac {2s} l$$$.
So, to solve this problem you need to calculate the number of leaves in the tree. This can be done in linear time by counting all degrees of vertices.
Time comlexity: $$$O(n)$$$.