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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, 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