- Practice
- Data Structures
- Disjoint Set
- Super Maximum Cost Queries

# Super Maximum Cost Queries

# Super Maximum Cost Queries

Victoria has a tree, , consisting of nodes numbered from to . Each edge from node to in tree has an integer weight, .

Let's define the cost, , of a path from some node to some other node as the maximum weight () for any edge in the unique path from node to node .

Victoria wants your help processing queries on tree , where each query contains integers, and , such that . For each query, she wants to print the number of different paths in that have a cost, , in the inclusive range .

It should be noted that path from some node to some other node is considered same as path from node to i.e is same as .

**Input Format**

The first line contains space-separated integers, (the number of nodes) and (the number of queries), respectively.

Each of the subsequent lines contain space-separated integers, , , and , respectively, describing a bidirectional road between nodes and which has weight .

The subsequent lines each contain space-separated integers denoting and .

**Constraints**

**Scoring**

- for of the test data.
- for of the test data.

**Output Format**

For each of the queries, print the number of paths in having cost in the inclusive range on a new line.

**Sample Input**

```
5 5
1 2 3
1 4 2
2 5 6
3 4 1
1 1
1 2
2 3
2 5
1 6
```

**Sample Output**

```
1
3
5
5
10
```

**Explanation**

:

:

:

:

...etc.