tolls — IATI junior
Task type: batch | Time limit: 0.25 s | Memory limit: 256 MB | Difficulty: 16
Algorithms: union-find, data structures, coordinate compression, sorting, prefix sum, binary search

![IATI Day 2, Junior group](_page_0_Picture_1.jpeg)

## Task 5. TOLLS ⏱️ 0.25 sec. 256 MB

In the country named Ivo, there are $N$ cities connected by $N - 1$ bidirectional highways and you can get from any city to any other city using the highways. Each highway connects two different cities $u_i$ and $v_i$ and it has a toll tax $w_i$, $1 \leq i \leq N - 1$. We will call "trip" a simple path (not containing duplicate cities) along the highways between two different cities $u$ and $v$. The costs for the trips in the country Ivo have been reduced and instead of paying the sum of the tolls along the trip, only one toll is paid, which is a maximal toll for a highway along the trip.

Ivaylo is responsible for the profits in the country. The government asked Ivaylo $Q$ questions for the sum of the costs of all the trips with costs in the interval $[l_j, r_j]$, $1 \leq j \leq Q$. It is guaranteed that the first question is for the sum of the costs of the trips between every two different cities, i.e. $l_1 = 1$ and $r_1 = \max_{1 \leq i \leq N-1}\{w_i\}$. Ivaylo cannot handle this task, calculating by hand, and because he cannot work with computers he requires that you write a program **tolls**, which calculates the answers to the questions.

## Input

The first line of the standard input contains two positive integers $N$ and $Q$ - the number of cities in the country Ivo and the number of questions given to Ivaylo. Each of the next $N - 1$ lines contains three positive integers $u_i$, $v_i$, $w_i$, which describe a highway between the cities $u_i$ and $v_i$ with toll $w_i$. Each of the rest $Q$ lines contains two positive integers $l_j$, $r_j$, which describe the questions given to Ivaylo.

## Output

For each question, in input order, output on a separate line the sum of the costs of the trips that are in the interval $[l_j, r_j]$.

## Constraints

*   $1 \leq N, Q \leq 10^5$
*   $1 \leq u_i, v_i \leq N$
*   $1 \leq w_i \leq 10^9$
*   $1 \leq l_j \leq r_j \leq 10^9$

![IATI Day 2, Junior group](_page_1_Picture_1.jpeg)

## Subtasks

| Subtask | Points | Required subtasks | $N$         | $Q$         | Other constraints          |
| :-------: | :----: | :----------------: | :----------: | :----------: | :--------------------------: |
|     1     |   0    |         −          |      −       |      −       | The example test.            |
|     2     |   5    |         1          |  $\leq 50$   |  $\leq 50$   |              −               |
|     3     |   5    |         −          | $\leq 10^3$  |     $= 1$    |              −               |
|     4     |   10   |        1 − 3       | $\leq 10^3$  | $\leq 100$  |              −               |
|     5     |   20   |         3          | $\leq 10^5$  |     $= 1$    |              −               |
|     6     |   10   |        1 − 5       | $\leq 10^5$  | $\leq 100$  |              −               |
|     7     |   20   |         −          | $\leq 10^5$  | $\leq 10^5$  | $l_j = 1, 1 \leq j \leq Q$ |
|     8     |   30   |        1 − 7       | $\leq 10^5$  | $\leq 10^5$  |              −               |

*The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.*

## Example

| Input | Output | Explanation of the example |
|---|---|---|
| 7 5 | 59 | Illustration of the cities and the highways: ![Illustration of the cities and the highways](_page_1_Picture_1.jpeg) |
| 1 2 1 | 32 | The count of the trips with cost 1 is 3: 1 – 2, 1 – 4, 2 – 4. |
| 3 1 3 | 56 | The count of the trips with cost 2 is 4: 1 – 5, 2 – 5, 3 – 6, 4 – 5. |
| 1 4 1 | 35 | The count of the trips with cost 3 is 8: 1 – 3, 1 – 6, 2 – 3, 2 – 6, 3 – 4, 3 – 5, 4 – 6, 5 – 6. |
| 4 5 2 | 56 | The count of the trips with cost 4 is 6: 1-7, 2-7, 3-7, 4-7, 5-7, 6-7. |
| 5 7 4 |  | The count of the trips with cost 5 is 0. |
| 3 6 2 |  | The answer to the first question is: $3 \times 1 + 4 \times 2 + 8 \times 3 + 6 \times 4 = 59$. |
| 1 4 |  | The answer to the second question is: $4 \times 2 + 8 \times 3 = 32$. |
| 2 3 |  | The answer to the third question is: $4 \times 2 + 8 \times 3 + 6 \times 4 = 56$. |
| 2 4 |  | The answer to the fourth question is: $3 \times 1 + 4 \times 2 + 8 \times 3 = 35$. |
| 1 3 |  | The answer to the fifth question is: $4 \times 2 + 8 \times 3 + 6 \times 4 + 0 \times 5 = 56$. |
| 2 5 |  |  |

Starter code: