P17450 同频回声 / Same Frequency Echo

给定一棵以节点 $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$ 位整数表示。

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

同频节点之间的同步代价如下： - 频段 $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$。