题目描述

给定一棵以节点 $1$ 为根、包含 $n$ 个节点的带权树。

节点 $i$ 具有：

• 频段 $c_i$；
• 发射时刻 $a_i$。

每个频段 $c$ 具有重要度 $w_c$。

对于两个使用相同频段的不同节点 $u,v$，定义它们的同步代价为

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

其中 $\operatorname{dist}(u,v)$ 表示 $u,v$ 之间简单路径上的边权之和。

一次询问给出节点 $x$ 和非负整数 $K$。

称频段 $c$ 在 $x$ 的管辖区域中产生了回声，当且仅当存在两个不同节点

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

满足

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

其中 $\operatorname{subtree}(x)$ 表示以 $x$ 为根的子树。

对于每次询问，求所有产生回声的频段的重要度之和，即

$$\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].$$

方括号表示 Iverson bracket：条件成立时取 $1$，否则取 $0$。

输入格式

第一行包含三个整数 $n,m,q$（$1\le n\le 10^6$，$1\le m\le 10^5$，$1\le q\le 10^6$），分别表示节点数、频段数和询问数。

第二行包含 $m$ 个整数 $w_1,w_2,\ldots,w_m$（$0\le w_c\le 10^9$），表示各个频段的重要度。

第三行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$1\le c_i\le m$），表示各节点使用的频段。

第四行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i\le 10^9$），表示各节点的发射时刻。

接下来 $n-1$ 行，每行包含三个整数 $u,v,d$（$1\le u,v\le n$，$0\le d\le 10^9$），表示节点 $u,v$ 之间存在一条边权为 $d$ 的无向边。

接下来 $q$ 行，每行包含两个整数 $x,K$（$1\le x\le n$，$0\le K\le 4\times 10^{18}$），表示一次询问。

保证输入的边构成一棵树，且答案能够用有符号 $64$ 位整数表示。

输出格式

对于每次询问，输出一行一个整数，表示答案。

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

提示

同频节点之间的同步代价如下：

• 频段 $1$ 的节点为 $1,3,6$：$D(1,3)=|10-13|+3=6$，$D(1,6)=|10-20|+5=15$，$D(3,6)=|13-20|+2=9$；
• 频段 $2$ 的节点为 $2,5$：$D(2,5)=|4-9|+1=6$；
• 频段 $3$ 的节点为 $4,7$：$D(4,7)=|8-7|+14=15$。

因此：

• 询问 $(1,5)$ 中没有频段产生回声，答案为 $0$；
• 询问 $(1,6)$ 中频段 $1,2$ 产生回声，答案为 $5+7=12$；
• 询问 $(2,6)$ 中只有频段 $2$ 产生回声，答案为 $7$；
• 询问 $(3,9)$ 中只有频段 $1$ 产生回声，答案为 $5$；
• 询问 $(1,15)$ 中三个频段均产生回声，答案为 $5+7+11=23$。