DMPG '19 G5 - Hunting the White Whale

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

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

If the white whale travels along these roads, it continually travels along a single path that sees a total of KK travelers per day, picked uniformly at random from all such paths. Doing so means that it will pass all locations that are on this path. Thus Rem asks Subaru NN questions: if we wait at node 1, 2, \dots, N1, 2, \dots, N, what is the probability we will encounter the whale?

Constraints

For all subtasks:

0 \le t_i \le 1\,000\,0000 \le t_i \le 1\,000\,000

Subtask 1 [9%]

1 \le N \le 1001 \le N \le 100

1 \le K \le 1001 \le K \le 100

The network of roads forms the simplest possible line: For 1 \le i < N1 \le i < N, road ii connects locations ii and i+1i+1.

Subtask 2 [12%]

1 \le N \le 1\,0001 \le N \le 1\,000

1 \le K \le 1\,000\,0001 \le K \le 1\,000\,000

Subtask 3 [22%]

1 \le N \le 200\,0001 \le N \le 200\,000

1 \le K \le 1001 \le K \le 100

Subtask 4 [57%]

1 \le N \le 200\,0001 \le N \le 200\,000

1 \le K \le 1\,000\,0001 \le K \le 1\,000\,000

Input Specification

The first line of input will contain two space-separated integers, NN and KK.
The next N-1N-1 lines will each contain 3 integers: a_i, b_i, t_ia_i, b_i, t_i, indicating there is a road between locations a_ia_i and b_ib_i, with t_it_i travelers per day.

Output Specification

You should output NN 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 42\to 3\to 4
  • 1\to 3\to 41\to 3\to 4
  • 5\to 4\to 35\to 4\to 3

Locations 33 and 44 appear on all 33 paths, but locations 11, 22, and 55 only appear on a single path each.


Comments


  • -6
    HyperGraphJ  commented on Nov. 1, 2020, 9:01 p.m. edit 3

    This comment is hidden due to too much negative feedback. Click here to view it.


  • 0
    Anshv2  commented on Aug. 13, 2020, 10:51 a.m. edited

    edit: nvm


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

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


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

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