You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

同频回声

题目描述

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

节点 $i$ 具有：

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

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

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

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

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

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

满足

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

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

方括号表示 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$。