DMPG '19 G5 - Hunting the White Whale - Olympiads Online Judge

DMPG '19 G5 - Hunting the White Whale

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$ ~N~ locations where the white whale has been rumoured to appear. There are $N-1$ ~N-1~ roads that connect every location to every other location. The $i$ ~i~th of these typically sees $t_i$ ~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$ ~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$ ~N~ questions: if we wait at node $1, 2, \dots, N$ ~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$ ~0 \le t_i \le 1\,000\,000~

Subtask 1 [9%]

$1 \le N \le 100$ ~1 \le N \le 100~

$1 \le K \le 100$ ~1 \le K \le 100~

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

Subtask 2 [12%]

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

$1 \le K \le 1\,000\,000$ ~1 \le K \le 1\,000\,000~

Subtask 3 [22%]

$1 \le N \le 200\,000$ ~1 \le N \le 200\,000~

$1 \le K \le 100$ ~1 \le K \le 100~

Subtask 4 [57%]

$1 \le N \le 200\,000$ ~1 \le N \le 200\,000~

$1 \le K \le 1\,000\,000$ ~1 \le K \le 1\,000\,000~

Input Specification

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

Output Specification

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

Sample Input

Sample Output

Explanation for Sample Output

The possible paths are:

$2\to 3\to 4$ ~2\to 3\to 4~
$1\to 3\to 4$ ~1\to 3\to 4~
$5\to 4\to 3$ ~5\to 4\to 3~

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

Comments

1

spheniscine commented on Jan. 25, 2025, 9:15 a.m. ← edited →

Just in case it isn't clear from the problem statement:

It may be possible that there are no paths that see a total of $K$ ~K~ travelers. [Perhaps the white whale is only a legend.] In this case, you should print 0 / 1 for all nodes.

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}$ ~\frac{0}{1}~ is a fraction in lowest terms