SOLVE
LATER
Given a weighted rooted tree with n vertices. Let's call simple path from u to v vertical iff \(u \ne v\) and u is on simple path from root to v. The weight of the path is a sum of weights for all edges in the path. The mean weight of the path is a weight of the path divided by number of edges in it. Calculate mean weight of each vertical path, sort them and print k-th value in sorted order.
The first line of input contains two integers n and k (\(2 \le n \le 10^{6}\)). It is guaranteed that there are at least k vertical paths in the given tree.
Next \(n-1\) lines contain description of edges \(u, v, c\) (\(1 \le u, v \le n, 1 \le c \le 10^{5}\)).
The root of the tree is vertex 1.
Print the k-th minimal mean weight as an irreducible fraction.
\(n \le 100~-\) 10 points
\(n \le 2000~-\) 10 points
\(n \le 15000\), \(k \le 10^{5}~-\) 15 points
\(n \le 15000~-\) 10 points
\(n \le 10^{5}~-\) 25 points
\(n \le 10^{6}, k \le 500~-\) 30 points
These are the vertical paths in the given tree: \(1 \rightarrow 2\), \(1 \rightarrow 2 \rightarrow 3\), \(1 \rightarrow 2 \rightarrow 4\), \(1 \rightarrow 5\), \(2 \rightarrow 3\) and \(2 \rightarrow 4\)
Mean weights of the paths:
\(f(1 \rightarrow 2) = 2\)
\(f(1 \rightarrow 2 \rightarrow 3) = \frac{4}{2} = 2\)
\(f(1 \rightarrow 2 \rightarrow 4) = \frac{5}{2}\)
\(f(1 \rightarrow 5) = 2\)
\(f(2 \rightarrow 3) = 2\)
\(f(2 \rightarrow 4) = 3\)
So, if we sort these values, we get: \(2, 2, 2, 2, \frac{5}{2}, 3\)