Problem I
Fika Optimization
The yearly programming contest LTH challenge is coming up, and as contest organizer you of course want the contestants (especially those from Lund) to perform as well as possible.
There are $M$ contestants competing from $N$ rooms. As contest organizer you know which room each contestant will be competing from, and it is possible that there are multiple contestants competing from the same room. The rooms are connected by $N - 1$ corridors such that there is a unique path between any two rooms. The corridors are all equally long and can be traversed in either direction.
As contest organizer you need to select one room to place all the snacks. You have noticed from previous contests that the location of the snacks room can affect the performance of the contestants. Specifically, for contestant number $i$ you estimate that the expected number of problems solved is $a_ i - \min (D, b_ i)$, where $D$ is the distance between the snacks room and the room that contestant $i$ is competing from, and $a_ i$ and $b_ i$ are two known integers satisfying $0 \leq b_ i \leq a_ i \leq 10^9$.
If you place the snacks room optimally, what is the maximum possible sum of problems solved by the $N$ contestants?
Input
The first line of input contains two integers $N$ and $M$ ($2 \leq N \leq 100,000$ and $1 \leq M \leq 200,000$).
The following $N - 1$ lines describe the corridors. Each such line contains two integers $u_ i$ and $v_ i$ ($1 \leq u_ i, v_ i \leq N$, $u_ i \ne v_ i$), which means there is a corridor between room $u_ i$ and room $v_ i$.
After that, the following $M$ lines describe the contestants. Each such line contains three integers $r_ i$, $a_ i$, and $b_ i$ ($1 \leq r_ i \leq N$ and $0 \leq b_ i \leq a_ i \leq 10^9$), meaning that there is a contestant in room number $r$ for which the expected number of problems solved if the snacks room is at distance $D$ would be $a_ i - min(D, b_ i)$.
Output
A single integer. The maximum sum of the expected number of problems solved if the snacks room is placed optimally.
Scoring
|
Group |
Points |
Constraints |
|
$1$ |
$19$ |
$N \leq 1000$ and $M \leq 2000$ |
|
$3$ |
$27$ |
$u_ i = i$ and $v_ i = i + 1$ for each $i \in \{ 1 \dots N - 1 \} $ (the rooms are connected in a line) |
|
$4$ |
$26$ |
The distance from room $1$ to any other room is at most $30$ |
|
$4$ |
$28$ |
No additional constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 1 2 2 3 3 1 3 3 2 3 3 |
8 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 3 3 5 3 6 1 2 3 4 1 3 4 6 5 6 5 3 2 4 4 |
11 |
