问题 D: Distance on Tree

链接：https://ac.nowcoder.com/acm/contest/57362/D
来源：牛客网
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 aia_iai for each $i=1,2,\dots ,n$.

Given a parameter $m$ and then $q$ queries, the $i$-th of which is represented by two numbers xix_ixi and kik_iki, your task is to maximize dis(u,v)+dis(v,w)+dis(w,u)dis(u,v)+dis(v,w)+dis(w,u)dis(u,v)+dis(v,w)+dis(w,u) by choosing three distinct nodes $u$, $v$ and $w$ in the subtree of xix_ixi such that au+av+aw≡ki(modm)a_u+a_v+a_w \equiv k_i \pmod mau+av+aw≡ki(modm). Here dis(u,v)dis(u,v)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\le n,m\le 2000$) and $q$ (1≤q≤2×1051 \le q \le 2 \times 10^51≤q≤2×105).
The second line contain $n$ integers a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an (0≤ai<m0 \le a_i < m0≤ai<m).
Following $n-1$ lines describe the tree, each of which contains three integers u,vu, vu,v (1≤u,v≤n1 \le u, v \le n1≤u,v≤n) and $w$ (1≤w≤2×1051 \le w \le 2 \times 10^51≤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 xix_ixi (1≤xi≤n1 \le x_i \le n1≤xi≤n) and kik_iki (0≤ki<m0 \le k_i < m0≤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