All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

October Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?