Problem Description

You are given a weighted tree with $n$ nodes rooted at node $1$.

Node $i$ has:

• frequency band $c_i$;
• transmission time $a_i$.

Each frequency band $c$ has an importance value $w_c$.

For two different nodes $u, v$ that use the same frequency band, define their synchronization cost as

$$D(u,v)=|a_u-a_v|+\operatorname{dist}(u,v),$$

where $\operatorname{dist}(u,v)$ is the sum of edge weights on the simple path between $u$ and $v$.

Each query provides a node $x$ and a non-negative integer $K$.

We say that frequency band $c$ produces an echo in the region governed by $x$ if and only if there exist two different nodes

$$u,v\in\operatorname{subtree}(x)$$

such that

$$c_u=c_v=c,\qquad D(u,v)\le K.$$

Here, $\operatorname{subtree}(x)$ denotes the subtree rooted at $x$.

For each query, compute the sum of importance values of all frequency bands that produce an echo:

$$\sum_{c=1}^{m} w_c \bigl[\exists\,u\ne v\in\operatorname{subtree}(x),\ c_u=c_v=c,\ D(u,v)\le K\bigr].$$

The square brackets denote the Iverson bracket: it equals $1$ if the condition holds, and $0$ otherwise.

Input Format

The first line contains three integers $n,m,q$ ($1\le n\le 10^6$, $1\le m\le 10^5$, $1\le q\le 10^6$), representing the number of nodes, the number of frequency bands, and the number of queries, respectively.

The second line contains $m$ integers $w_1,w_2,\ldots,w_m$ ($0\le w_c\le 10^9$), representing the importance value of each frequency band.

The third line contains $n$ integers $c_1,c_2,\ldots,c_n$ ($1\le c_i\le m$), representing the frequency band used by each node.

The fourth line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i\le 10^9$), representing the transmission time of each node.

The next $n-1$ lines each contain three integers $u,v,d$ ($1\le u,v\le n$, $0\le d\le 10^9$), indicating an undirected edge between nodes $u$ and $v with weight$d$.

The next $q$ lines each contain two integers $x,K$ ($1\le x\le n$, $0\le K\le 4\times 10^{18}$), representing one query.

It is guaranteed that the edges form a tree, and that the answer fits in a signed $64$-bit integer.

Output Format

For each query, output one integer per line, representing the answer.

7 3 5
5 7 11
1 2 1 3 2 1 3
10 4 13 8 9 20 7
1 2 2
1 3 3
2 4 4
2 5 1
3 6 2
3 7 5
1 5
1 6
2 6
3 9
1 15

0
12
7
5
23

Hint

The synchronization costs between nodes with the same frequency are as follows:

• Nodes on frequency band $1$ are $1,3,6$: $D(1,3)=|10-13|+3=6$, $D(1,6)=|10-20|+5=15$, $D(3,6)=|13-20|+2=9$.
• Nodes on frequency band $2$ are $2,5$: $D(2,5)=|4-9|+1=6$.
• Nodes on frequency band $3$ are $4,7$: $D(4,7)=|8-7|+14=15$.

Therefore:

• In query $(1,5)$, no frequency band produces an echo, so the answer is $0$.
• In query $(1,6)$, frequency bands $1,2$ produce echoes, so the answer is $5+7=12$.
• In query $(2,6)$, only frequency band $2$ produces an echo, so the answer is $7$.
• In query $(3,9)$, only frequency band $1$ produces an echo, so the answer is $5$.
• In query $(1,15)$, all three frequency bands produce echoes, so the answer is $5+7+11=23$.

Translated by ChatGPT 5