CF960H.Santa's Gift

Santa has an infinite number of candies for each of $m$ flavours. You are given a rooted tree with $n$ vertices. The root of the tree is the vertex $1$. Each vertex contains exactly one candy. The $i$-th vertex has a candy of flavour $f_i$.

Sometimes Santa fears that candies of flavour $k$ have melted. He chooses any vertex $x$ randomly and sends the subtree of $x$ to the Bakers for a replacement. In a replacement, all the candies with flavour $k$ are replaced with a new candy of the same flavour. The candies which are not of flavour $k$ are left unchanged. After the replacement, the tree is restored.

The actual cost of replacing one candy of flavour $k$ is $c_k$ (given for each $k$). The Baker keeps the price fixed in order to make calculation simple. Every time when a subtree comes for a replacement, the Baker charges $C$, no matter which subtree it is and which flavour it is.

Suppose that for a given flavour $k$ the probability that Santa chooses a vertex for replacement is same for all the vertices. You need to find out the expected value of error in calculating the cost of replacement of flavour $k$. The error in calculating the cost is defined as follows.

$$Error\\ E(k) =\\ (Actual Cost\\ –\\ Price\\ charged\\ by\\ the\\ Bakers) ^ 2.$$

Note that the actual cost is the cost of replacement of one candy of the flavour $k$ multiplied by the number of candies in the subtree.

Also, sometimes Santa may wish to replace a candy at vertex $x$ with a candy of some flavour from his pocket.

You need to handle two types of operations:

• Change the flavour of the candy at vertex $x$ to $w$.
• Calculate the expected value of error in calculating the cost of replacement for a given flavour $k$.

圣诞老人拥有 $m$ 种口味的糖果，每种口味数量无限。你被给定一棵含 $n$ 个顶点的有根树，树的根节点为顶点 $1$。每个顶点上恰好有一颗糖果，其中第 $i$ 个顶点上的糖果口味为 $f_i$。

有时圣诞老人担心口味为 $k$ 的糖果已经融化。此时他随机选择任意一个顶点 $x$，并将以 $x$ 为根的子树送至面包师处进行更换。在更换过程中，子树中所有口味为 $k$ 的糖果均被替换为一颗同口味的新糖果；而口味不为 $k$ 的糖果则保持不变。更换完成后，树恢复原状。

更换一颗口味为 $k$ 的糖果的实际成本为 $c_k$（对每个 $k$ 均已给出）。为简化计算，面包师将每次更换的价格固定为 $C$，即无论送来的是哪棵子树、也不论所涉及的口味为何，收费均为 $C$。

假设对于给定的口味 $k$，圣诞老人选择任一顶点进行更换的概率对所有顶点均相等。你需要计算：针对口味 $k$，更换成本计算误差的期望值。此处“计算误差”定义如下：

$$Error\\ E(k) =\\ (Actual Cost\\ –\\ Price\\ charged\\ by\\ the\\ Bakers) ^ 2.$$

注意：实际成本等于单颗口味为 $k$ 的糖果的更换成本 $c_k$ 乘以该子树中口味为 $k$ 的糖果总数。

此外，圣诞老人有时也可能希望用自己口袋中某口味的糖果来替换顶点 $x$ 处的糖果。

你需要处理两种操作：

• 将顶点 $x$ 处糖果的口味修改为 $w$；
• 计算针对给定口味 $k$ 的更换成本计算误差的期望值。

The first line of the input contains four integers $n$ ($2 \leqslant n \leqslant 5 \cdot 10^4$), $m$, $q$, $C$ ($1 \leqslant m, q \leqslant 5 \cdot 10^4$, $0 \leqslant C \leqslant 10^6$) — the number of nodes, total number of different flavours of candies, the number of queries and the price charged by the Bakers for replacement, respectively.

The second line contains $n$ integers $f_1, f_2, \dots, f_n$ ($1 \leqslant f_i \leqslant m$), where $f_i$ is the initial flavour of the candy in the $i$-th node.

The third line contains $n - 1$ integers $p_2, p_3, \dots, p_n$ ($1 \leqslant p_i \leqslant n$), where $p_i$ is the parent of the $i$-th node.

The next line contains $m$ integers $c_1, c_2, \dots c_m$ ($1 \leqslant c_i \leqslant 10^2$), where $c_i$ is the cost of replacing one candy of flavour $i$.

The next $q$ lines describe the queries. Each line starts with an integer $t$ ($1 \leqslant t \leqslant 2$) — the type of the query.

If $t = 1$, then the line describes a query of the first type. Two integers $x$ and $w$ follow ($1 \leqslant  x \leqslant  n$, $1 \leqslant  w \leqslant m$), it means that Santa replaces the candy at vertex $x$ with flavour $w$.

Otherwise, if $t = 2$, the line describes a query of the second type and an integer $k$ ($1 \leqslant k \leqslant m$) follows, it means that you should print the expected value of the error in calculating the cost of replacement for a given flavour $k$.

The vertices are indexed from $1$ to $n$. Vertex $1$ is the root.

输入的第一行包含四个整数 $n$（$2 \leqslant n \leqslant 5 \cdot 10^4$）、$m$、$q$、$C$（$1 \leqslant m, q \leqslant 5 \cdot 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$ 的替换成本时，误差的期望值。

顶点编号从 $1$ 到 $n$。顶点 $1$ 是根节点。

Output the answer to each query of the second type in a separate line.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. The checker program considers your answer correct if and only if $\frac{|a-b|}{max(1,b)}\leqslant 10^{-6}$.

对每个第二类查询，输出答案，每个答案占一行。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设你的答案为 $a$，评测机的答案为 $b$。当且仅当 $\frac{|a-b|}{\max(1,b)}\leqslant 10^{-6}$ 时，评测程序判定你的答案正确。

For $1$-st query, the error in calculating the cost of replacement for flavour $1$ if vertex $1$, $2$ or $3$ is chosen are $66^2$, $66^2$ and $(-7)^2$ respectively. Since the probability of choosing any vertex is same, therefore the expected value of error is $\frac{66^2+66^2+(-7)^2}{3}$.

Similarly, for $2$-nd query the expected value of error is $\frac{41^2+(-7)^2+(-7)^2}{3}$.

After $3$-rd query, the flavour at vertex $2$ changes from $1$ to $3$.

For $4$-th query, the expected value of error is $\frac{(-7)^2+(-7)^2+(-7)^2}{3}$.

Similarly, for $5$-th query, the expected value of error is $\frac{89^2+41^2+(-7)^2}{3}$.

对于第 $1$ 次查询，若选择顶点 $1$、$2$ 或 $3$ 来计算口味 $1$ 的替换代价，所产生的误差分别为 $66^2$、$66^2$ 和 $(-7)^2$。由于选择任意顶点的概率相同，因此误差的期望值为 $\frac{66^2+66^2+(-7)^2}{3}$。

类似地，对于第 $2$ 次查询，误差的期望值为 $\frac{41^2+(-7)^2+(-7)^2}{3}$。

第 $3$ 次查询后，顶点 $2$ 处的口味由 $1$ 变为 $3$。

对于第 $4$ 次查询，误差的期望值为 $\frac{(-7)^2+(-7)^2+(-7)^2}{3}$。

类似地，对于第 $5$ 次查询，误差的期望值为 $\frac{89^2+41^2+(-7)^2}{3}$。