manypairs — EJOI contest
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 21
Algorithms: hash map, dynamic programming, data structures, tree, tree dp

![](_page_0_Picture_0.jpeg)

# Many Pairs

EJOI-land is a kingdom consisting of $N$ cities. Each city has a unique index between 1 and $N$ associated with it. The cities are connected by $N − 1$ bidirectional roads. It is also guaranteed that you can reach any city from any other city. In other words, EJOI-land has a tree-like structure. There are also $K$ trading treaties in EJOI-land. Each treaty is defined by a pair of cities $(A, B)$ and has cost $C$ associated with it.

The king decided to test his son's governing abilities as follows:

*   He will choose a city $H$ and designate it as the prince's headquarters. Suppose that the tree will now be rooted in $H$.
*   The prince will choose **at most** two cities that are neighbours of $H$. Now $H$ and the subtrees of the chosen cities are under his governance.

The profit he gets is equal to the sum of the costs $C$ of the treaties under his jurisdiction, for a treaty to be under his jurisdiction, both cities associated with it must be under his governance.

The king still hasn't announced which city will be the prince's headquarters, but the prince still likes to wonder. Thus, for each city, he wonders what is the maximal profit he can get if it were to be chosen as the new headquarters.

Your task is to find the maximal profit for each city.

## Input

The first line of input contains two space-separated integers, $N$ and $K$, the number of cities in EJOI-land, and the number of trading treaties, respectively.

The following $N − 1$ lines each contain two space-separated integers $U$ and $V$, meaning that there is a road between cities $U$ and $V$.

The following $K$ lines each contain three space-separated integers $A$, $B$, and $C$ – being the two cities involved in the treaty, and its cost, respectively.

## Output

Output $N$ space-separated integers, the $i$-th integer representing the maximal profit obtainable if city $i$ were to be chosen as the prince's headquarters.

## Example

| Input    | Output              |
| :------- | :------------------ |
| `6 4`    | `51 51 51 51 51 33` |
| `6 2`    |                     |
| `2 5`    |                     |
| `3 6`    |                     |
| `1 2`    |                     |
| `4 6`    |                     |
| `2 5 11` |                     |
| `5 6 16` |                     |
| `4 3 18` |                     |
| `2 3 6`  |                     |

With the 6th city as the headquarters, the prince has three ways of choosing the two neighbouring cities and their respective subtrees:

*   Cities 2 and 3
*   Cities 2 and 4
*   Cities 3 and 4

By choosing to govern over cities 2 and 3, the prince gets the treaties 1, 2, and 4 under his jurisdiction. Thus, he gets the profit 11 + 16 + 6 = 33.

## Constraints and Scoring

*   $2 \le N, K \le 2 \cdot 10^5$
*   $1 \le U, V, A, B \le N$
*   $1 \le C \le 10^6$

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.

| Group | Score | Limits                    |
| :---- | :---- | :------------------------ |
| 1     | 12    | $N, K \le 50$             |
| 2     | 13    | $N \le 5000, K \le 500$   |
| 3     | 17    | $N \le 5000, K \le 2000$  |
| 4     | 21    | $N, K \le 5000$           |
| 5     | 37    | No further constraints    |

Starter code: