Tree Broadcast - Repovive Starter Round 7 | Repovive

21G. Tree Broadcast

3500 pts2s256 MB

You are given a network of $n$ servers, numbered from $1$ to $n$ . The network has $n-1$ links and forms a tree.

Transmitting an entire file through link $i$ takes exactly $w_i$ seconds.

Initially, exactly one server has the complete file. File transmissions follow these rules:

A server can transmit the file only after it has received the complete file.
During a transmission, both endpoints of the link are busy.
A server can participate in at most one transmission at any moment.
Transmissions using disjoint pairs of servers can happen simultaneously.
A transmission cannot be paused.

For each $s$ with $1 \le s \le n$ , independently suppose that server $s$ is the only server that has the file initially. Find the minimum time needed for every server to receive the complete file.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$1 \le u_i, v_i \le n$
$u_i \ne v_i$
$1 \le w_i \le 10^9$
The given links form a tree

Input

t

\left. \begin{array}{l} n \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \quad w_{n-1} \end{array} \right\} \times t

Output

For each test case, output the minimum required time for every possible initially informed server:

\left. \begin{array}{l} ans_1 \quad ans_2 \quad \cdots \quad ans_n \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

2
1 2 7

Case 3

3
1 2 2
2 3 5

Case 4

Case 5

Explanation

Case 1

The only server already has the file, so no transmission is needed.

Case 2

The file must cross the only link, which takes $7$ seconds, regardless of the starting server.

Case 3

Starting from an endpoint, the two transmissions take $2+5=7$ seconds. Starting from server $2$ , both links must be used one after the other, so the same total is required.

Case 4

Starting from server $1$ , first send to server $2$ and then to server $3$ . The two transmissions of length $10$ can then overlap, and all servers are informed after $12$ seconds. Similar schedules work from servers $2$ and $3$ . From server $4$ or $5$ , the file must travel along the full weighted path of length $22$ to reach the other endpoint.

Case 5

Starting from server $1$ , send to server $2$ first. The transmissions from $2$ to $4$ and from $1$ to $3$ can then happen simultaneously, finishing at time $101$ . The same is possible from server $2$ . From either endpoint, the file must traverse the full path, whose total weight is $201$ .

Output

Case 1

Case 2

7 7

Case 3

7 7 7

Case 4

12 12 12 22 22

Case 5

101 101 201 201

You are given a network of $n$ servers, numbered from $1$ to $n$ . The network has $n-1$ links and forms a tree.

Transmitting an entire file through link $i$ takes exactly $w_i$ seconds.

Initially, exactly one server has the complete file. File transmissions follow these rules:

A server can transmit the file only after it has received the complete file.
During a transmission, both endpoints of the link are busy.
A server can participate in at most one transmission at any moment.
Transmissions using disjoint pairs of servers can happen simultaneously.
A transmission cannot be paused.

For each $s$ with $1 \le s \le n$ , independently suppose that server $s$ is the only server that has the file initially. Find the minimum time needed for every server to receive the complete file.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$1 \le u_i, v_i \le n$
$u_i \ne v_i$
$1 \le w_i \le 10^9$
The given links form a tree

t

\left. \begin{array}{l} n \\ u_1 \quad v_1 \quad w_1 \\ u_2 \quad v_2 \quad w_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \quad w_{n-1} \end{array} \right\} \times t

For each test case, output the minimum required time for every possible initially informed server:

\left. \begin{array}{l} ans_1 \quad ans_2 \quad \cdots \quad ans_n \end{array} \right\} \times t

The file must cross the only link, which takes $7$ seconds, regardless of the starting server.

Starting from an endpoint, the two transmissions take $2+5=7$ seconds. Starting from server $2$ , both links must be used one after the other, so the same total is required.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

21G. Tree Broadcast

Constraints

Input

Output

Samples

21G. Tree Broadcast

Constraints

Input

Output

Samples