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 N locations where the white whale has been rumoured 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.

If the white whale travels along these roads, it continually travels along a single path that sees a total of K 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 N questions: if we wait at node 1, 2, \dots, 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%]

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%]

1 \le N \le 1\,000

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

Subtask 3 [22%]

1 \le N \le 200\,000

1 \le K \le 100

Subtask 4 [57%]

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 a 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


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

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


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

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