K-th mean path

★★★★★

2.5

2 votes

Data Structures, Fenwick Tree, Fenwick tree, Hard

Details

Submissions

Discussion

Editorial

Problem

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

Sample Input

Sample Output

5/2

Time Limit: 5

Memory Limit: 512

Source Limit:

Explanation

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$

Contributers:

Alex Danilyuk

Niyaz Nigmatullin