同频回声

题目描述

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

节点 $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$ 之间简单路径^[2]上的边权之和。

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

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

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

满足

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

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

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

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

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

输入格式

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

第二行包含 $m$ 个整数 $w_1,w_2,\ldots,w_m(0\le w_c\le10^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\le10^9),$ 表示各节点的发射时刻。

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

接下来 $q$ 行，每行包含两个整数 $x,K(1\le x\le n,\ 0\le K\le4\times10^{18})$，表示一次询问。

输出格式

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

样例

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$。

---

1. 一棵有 $n$ 个节点的树可以表示为 $T(V, E)$，其中 $|V| = n, |E| = n - 1$，且 $E \subseteq\{\{u, v\} | u, v \in V\}$，且对于所有的 $u, v \in V, u \neq v$，存在 $u = p_0, p_1, \dots, p_k = v$ 且 $\{p_{i - 1}, p_i\} \in E$ 对所有的 $i = 1, 2, \dots, k$ 成立。其中，$V$ 中的元素称为顶点，$E$ 中的元素称为边。节点 $u$ 和节点 $v$ 相邻当且仅当 $\{u, v\} \in E$。 ↩︎

2. 指的是 $u = p_0, \dots, p_k = v$，且 $\forall i \neq j, p_i \neq p_j$，且 $\{p_{i - 1}, p_i\} \in E$ 对 $\forall i = 1, 2, \dots, k$ 成立。 ↩︎

3. $v$ 在 $u$ 的子树中当且仅当 $u$ 在根到 $v$ 的简单路径上。 ↩︎