P4074 [WC2013] 糖果公园

题目描述

给出 $n$ 个点 、 $n - 1$ 条无向边的树。

有 $m$ 种糖果，第 $i$ 种糖果的美味指数为 $V_i$。

树上每个点只提供一种糖果$C_i$（会动态修改），游客在一个点只能领取一个糖果。游客品尝 糖果 $C_i$ 的愉悦指数为 $V_{C_i} \times W_k$ ，$W_k$ 为游客第 $k$ 次品尝同种糖果的新奇指数，$k$越大，$W_k$ 越小，可以理解为同种糖果吃多了就没有那么愉悦了。

有 $q$ 次操作。每次操作有修改 或 询问两种：

$0$ $x$ $c$：表示将点 $x$ 发放的糖果类型改为 $c$；

$1$ $x$ $y$：表示从点 $x$ 出发到点 $y$ 的简单路径上品尝糖果的愉悦指数总和 。

输入格式

第一行包含三个正整数 $n, m, q$， 分别表示游览点个数、 糖果种类数和操作次数。

第二行包含 $m$ 个正整数 $V_1, V_2, \ldots, V_m$。

第三行包含 $n$ 个正整数 $W_1, W_2, \ldots, W_n$。

第四行到第 $n + 2$ 行，每行包含两个正整数 $A_i, B_i$，表示这两个游览点之间有路径可以直接到达。

第 $n + 3$ 行包含 $n$ 个正整数 $C_1, C_2, \ldots, C_n$。

接下来 $q$ 行， 每行包含三个整数 $Type, x, y$，表示一次操作：

• 若 $Type$ 为 $0$，则 $1 \leq x \leq n$， $1 \leq y \leq m$，表示将编号为 $x$ 的游览点发放的糖果类型改为 $y$；
• 若 $Type$ 为 $1$，则 $1 \leq x, y \leq n$，表示对出发点为 $x$，终止点为 $y$ 的路线询问愉悦指数。

输出格式

按照输入的先后顺序，对于每个 $Type$ 为 $1$ 的操作输出一行，用一个正整数表示答案。

输入输出样例 #1

输入 #1

4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2

输出 #1

84
131
27
84

说明/提示

【样例解释】

我们分别用

代表 $C_i$ 为 $1$、 $2$、 $3$ 的节点，在修改之前：

在将 $C_2$ 修改为 $1$ 之后：

【数据规模与约定】

对于所有的数据： $1 \leq V_i, W_i \leq 10^6$，$1 \leq A_i, B_i \leq n$， $1 \leq C_i \leq m$， $W_1, W_2, \ldots, W_n$ 是非递增序列，即对任意 $1 < i \leq n$， 满足 $W_i \le W_{i-1}$。

其它的限制条件如下表所示：