DMPG '19 G5 - Hunting the White Whale - DMOJ: Modern 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 \leq t_{i} \leq 1 000 000$

Subtask 1 [9%]

$1 \le N \le 100$ $1 \leq N \leq 100$

$1 \le K \le 100$ $1 \leq K \leq 100$

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

Subtask 2 [12%]

$1 \le N \le 1\,000$ $1 \leq N \leq 1 000$

$1 \le K \le 1\,000\,000$ $1 \leq K \leq 1 000 000$

Subtask 3 [22%]

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

$1 \le K \le 100$ $1 \leq K \leq 100$

Subtask 4 [57%]

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

$1 \le K \le 1\,000\,000$ $1 \leq K \leq 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

Copy

Sample Output

Copy

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 61 days ago ← 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