CF960H Santa's Gift

圣诞老人拥有每种口味 $m$ 的无限糖果。给定一棵包含 $n$ 个顶点的有根树，根节点为顶点 $1$。每个顶点恰好包含一颗糖果，第 $i$ 个顶点的糖果口味为 $f_i$。 有时圣诞老人担心口味 $k$ 的糖果可能融化。他会随机选择一个顶点 $x$，并将 $x$ 的子树交给面包师进行替换。在替换过程中，所有口味 $k$ 的糖果会被替换为同口味的新糖果，其他口味的糖果保持不变。替换完成后，树会恢复原状。 替换一颗口味 $k$ 糖果的实际成本为 $c_k$（每个 $k$ 给定）。面包师为简化计算保持固定收费价格 $C$。每次子树进行替换时，无论子树大小或口味如何，面包师都收取 $C$ 的费用。 假设对于给定口味 $k$，圣诞老人选择替换顶点的概率在所有顶点中均匀分布。你需要计算口味 $k$ 替换成本计算误差的期望值。误差定义如下： $$ E(k) = (\text{实际成本} - \text{面包师收取价格})^2 $$ 注意实际成本等于单颗口味 $k$ 糖果替换成本乘以子树中该口味糖果数量。 此外，圣诞老人可能希望用口袋中的糖果替换顶点 $x$ 处的糖果。你需要处理两种操作： - 将顶点 $x$ 的糖果口味改为 $w$ - 计算给定口味 $k$ 替换成本误差的期望值

第一行包含四个整数 $n$（$2 \leqslant n \leqslant 5 \times 10^4$）、$m$、$q$、$C$（$1 \leqslant m, q \leqslant 5 \times 10^4$，$0 \leqslant C \leqslant 10^6$）—— 分别表示节点数、糖果口味总数、询问次数和面包师收取的固定费用。 第二行包含 $n$ 个整数 $f_1, f_2, \dots, f_n$（$1 \leqslant f_i \leqslant m$），其中 $f_i$ 表示第 $i$ 个节点初始糖果口味。 第三行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \leqslant p_i \leqslant n$），其中 $p_i$ 是第 $i$ 个节点的父节点。 第四行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$1 \leqslant c_i \leqslant 10^2$），其中 $c_i$ 表示替换单颗口味 $i$ 糖果的成本。 接下来 $q$ 行描述询问。每行以整数 $t$（$1 \leqslant t \leqslant 2$）开头表示询问类型： - 若 $t=1$，表示修改操作，后接两个整数 $x$ 和 $w$（$1 \leqslant x \leqslant n$，$1 \leqslant w \leqslant m$），表示将顶点 $x$ 的糖果口味改为 $w$ - 若 $t=2$，表示计算操作，后接整数 $k$（$1 \leqslant k \leqslant m$），要求输出口味 $k$ 的替换成本误差期望值

对每个第二类询问，输出一行答案。答案的绝对或相对误差不超过 $10^{-6}$ 即视为正确。

对于第一个询问，当选择顶点 $1$、$2$ 或 $3$ 时，口味 $1$ 的替换误差分别为 $66^2$、$66^2$ 和 $(-7)^2$。由于选择概率均等，期望值为 $\frac{66^2 + 66^2 + (-7)^2}{3}$。 类似地，第二个询问的期望值为 $\frac{41^2 + (-7)^2 + (-7)^2}{3}$。 第三个询问后，顶点 $2$ 的口味从 $1$ 变为 $3$。 第四个询问的期望值为 $\frac{(-7)^2 + (-7)^2 + (-7)^2}{3}$。 第五个询问的期望值为 $\frac{89^2 + 41^2 + (-7)^2}{3}$。 翻译由 DeepSeek R1 完成