## OCC '19 G6 - Monkeys in a Tree

View as PDF

Points: 30
Time limit: 2.75s
Memory limit: 512M

Problem types

In DMOJ forest, there is a tree with nodes, conveniently numbered from to , connected by weighted edges. The edge connects nodes and with distance . On each node, a monkey lives there. The monkey at node has a ranking . Multiple monkeys may have the same ranking.

Monkey king plans to host a banana eating competition. He picks up a node as the location and invites monkeys whose rankings are within (i.e. ) to attend this event. Monkey king wants to figure out the sum of distances for all invited monkeys travelling to . Since monkey king hasn't found out the best location, he will ask you queries. In the query, he will give you , and . You need to tell him the sum of distances for monkeys with rankings in travelling to . Because monkey king is quite impatient, you must answer his queries online.

#### Input Specification

The first line contains three integers, , , and (, , ), where is the number of nodes in the tree, is the number of queries, and is used to decode each query.

The second line contains integers, , (), the ranking of the monkey.

Each of the following lines contains three integers, , and , (, ), an edge between nodes and with length .

lines of input follow. The line contains three integers, , and , where and are the encoded ranking interval. You can get the actual and by calculating and , where is the answer for the previous query, and specially for the first query.

#### Output Specification

Print lines. The line contains an integer, the sum of distances for the query.

#### Sample Input

10 5 10
0 0 7 2 1 4 7 7 7 9
1 2 5
2 3 3
1 4 4
2 5 6
4 6 5
3 7 2
1 8 7
6 9 3
7 10 4
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7

#### Sample Output

21
75
61
117
68

#### Constraints

For all test cases, , , .