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.
Input Format
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.
Output Format
Print the k-th minimal mean weight as an irreducible fraction.
Scoring
\(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\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor