问题 D: Distance on Tree
内存限制:512 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
You are given a rooted tree with n nodes labeled from 1 to n, the root of which is the 1-st node, and the
i-th node has a given value ai for each i = 1, 2, . . . , n.
Given a parameter m and then q queries, the i-th of which is represented by two numbers xi and ki
,
your task is to maximize dis(u, v) + dis(v, w) + dis(w, u) by choosing three distinct nodes u, v and w in
the subtree of xi such that au + av + aw ≡ ki (mod m). Here dis(u, v) is the length of the shortest path
between the u-th and the v-th nodes on the tree. If there is no solution for a query, the answer is 0.
输入
The first line contains three integers n, m (1 ≤ n, m ≤ 2 000) and q (1 ≤ q ≤ 2 × 105
).
The second line contain n integers a1, a2, . . . , an (0 ≤ ai < m).
Following n − 1 lines describe the tree, each of which contains three integers u, v (1 ≤ u, v ≤ n) and w
(1 ≤ w ≤ 2 × 105
), representing an edge with length w between the u-th and the v-th nodes.
In the following q lines, the i-th line contains two integers xi (1 ≤ xi ≤ n) and ki (0 ≤ ki < m), describing
the i-th query.
输出
Output q lines, the i-th of which contains an integer, indicating the answer to the i-th query.
样例输入 复制
5 5 10
0 1 2 3 4
1 2 1
2 3 2
2 4 3
1 5 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
样例输出 复制
12
14
16
16
20
0
10
0
0
0