OCC '19 G6 - Monkeys in a Tree

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.75s
Memory limit: 512M

Problem types

In DMOJ forest, there is a tree with N nodes, conveniently numbered from 1 to N, connected by N-1 weighted edges. The i^\text{th} edge connects nodes u_i and v_i with distance w_i. On each node, a monkey lives there. The monkey at node i has a ranking r_i. Multiple monkeys may have the same ranking.

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

Constraints

For all subtasks:

1 \le N \le 150\,000

1 \le Q \le 200\,000

1 \le M \le 10^9

Subtask Points Additional constraints
1 19 N \le 3000, Q \le 300, M \le 10^9
2 21 N \le 10^5, Q \le 10^5, M \le 20
3 23 N \le 10^5, Q \le 10^5, M \le 10^9
4 37 No additional constraints.

Input Specification

The first line contains three integers, N, Q, and M (1 \le N \le 150\,000, 1 \le Q \le 200\,000, 1 \le M \le 10^9), where N is the number of nodes in the tree, Q is the number of queries, and M is used to decode each query.

The second line contains N integers, r_i, (0 \le r_i < M), the ranking of the i^\text{th} monkey.

Each of the following N-1 lines contains three integers, u_i, v_i and w_i, (1 \le u_i, v_i \le N, 1 \le w_i \le 1\,000), an edge between nodes u_i and v_i with length w_i.

Q lines of input follow. The i^\text{th} line contains three integers, X_i, l_i and r_i, where l_i and r_i are the encoded ranking interval. You can get the actual L_i and R_i by calculating L_i = \min((l_i + \text{lastans}) \mathbin\% M, (r_i + \text{lastans}) \mathbin\% M) and R_i = \max((l_i + \text{lastans}) \mathbin\% M, (r_i + \text{lastans}) \mathbin\% M), where \text{lastans} is the answer for the previous query, and specially \text{lastans} = 0 for the first query.

Output Specification

Print Q lines. The i^\text{th} line contains an integer, the sum of distances for the i^\text{th} 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

Comments

There are no comments at the moment.