DMPG '19 G5 - Hunting the White Whale

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 4.5s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Subaru and Rem are hunting down the white whale. They currently have a list of N locations where the white whale has been known to appear. There are N-1 roads that connect every location to every other location. The ith of these typically sees t_i travelers per day.

Rem notices that the white whale also travels along these roads; specifically it continually travels along a single path that sees a total of K travelers per day. Doing so means that it will pass all locations that are on this path. Thus Rem asks Subaru N questions: if we wait at node 1, 2, \ldots, N-1, N, what is the probability we will encounter the whale?

Constraints

For all subtasks, 0 \le t_i \le 1\,000\,000

Subtask 1 (9 points)
  • 1 \le N \le 100
  • 1 \le K \le 100
  • The network of roads forms the simplest possible line: For 1 \le i < N, road i connects locations i and i+1.
Subtask 2 (12 points)
  • 1 \le N \le 1\,000
  • 1 \le K \le 1\,000\,000
Subtask 3 (22 points)
  • 1 \le N \le 200\,000
  • 1 \le K \le 100
Subtask 4 (57 points)
  • 1 \le N \le 200\,000
  • 1 \le K \le 1\,000\,000

Input Specification

The first line of input will contain two space-separated integers, N and K.
The next N-1 lines will each contain 3 integers: a_i, b_i, t_i, indicating there is an road between locations a_i and b_i, with t_i travelers per day.

Output Specification

You should output N lines, where each is the probability Rem and Subaru encounter the white whale, expressed as a fraction in lowest terms.

Sample Input

5 4
1 3 3
2 3 3
3 4 1
4 5 3

Sample Output

1 / 3
1 / 3
1 / 1
1 / 1
1 / 3

Explanation for Sample Output

The possible paths are:

  • 2\to 3\to 4
  • 1\to 3\to 4
  • 5\to 4\to 3

Locations 3 and 4 appear on all 3 paths, but locations 1, 2, and 5 only appear on a single path each.


Comments


  • 5
    discoverMe  commented on June 9, 2019, 12:07 a.m.

    what if a path has no chance? should it be 0 / 1?


    • 5
      Plasmatic  commented on June 9, 2019, 12:09 a.m.

      \frac{0}{1} is a fraction in lowest terms