K-th mean path
Tag(s):

## Data Structures, Fenwick Tree, Hard

Problem
Editorial
Analytics

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
5 5
1 2 2
1 5 2
2 3 2
2 4 3

SAMPLE OUTPUT
5/2

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$

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

October Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Math > Number Theory
• Algorithms > Graphs