English · Original
Chinese · Translation
Formal · Original
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$.
## Input
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.
## Output
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}$.
[samples]
## Note
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}$.
Santa 有无限数量的每种 $m$ 种口味的糖果。你得到一棵包含 $n$ 个顶点的有根树。树的根是顶点 $1$。每个顶点恰好包含一颗糖果。第 $i$ 个顶点的糖果口味为 $f_i$。
有时 Santa 担心口味为 $k$ 的糖果融化了。他随机选择任意一个顶点 $x$，并将 $x$ 的子树发送给 Baker 进行更换。在更换过程中，所有口味为 $k$ 的糖果都会被替换为同一种新口味的糖果，而其他非 $k$ 口味的糖果保持不变。更换完成后，树被恢复。
更换一颗口味为 $k$ 的糖果的 _实际_ 成本为 $c_k$（每个 $k$ 均给出）。Baker 为简化计算而固定价格。每当有子树前来更换时，Baker 都会收取固定费用 $C$，无论子树是哪个、口味是哪种。
假设对于给定的口味 $k$，Santa 选择任一顶点进行更换的概率均等。你需要计算计算口味 $k$ 更换成本的 _误差_ 的期望值。误差定义如下：
$$ Error\ E(k) =\ (实际成本\ –\ Baker 收取的价格) ^ 2.$$
注意，实际成本是更换一颗口味为 $k$ 的糖果的成本乘以子树中糖果的数量。
此外，有时 Santa 可能希望用他口袋中某种口味的糖果替换顶点 $x$ 上的糖果。
你需要处理两种操作：
输入的第一行包含四个整数 $n$ ($2 lt.eq.slant n lt.eq.slant 5 dot.op 10^4$)、$m$、$q$、$C$ ($1 lt.eq.slant m, q lt.eq.slant 5 dot.op 10^4$, $0 lt.eq.slant C lt.eq.slant 10^6$) —— 分别表示节点数、糖果总口味数、查询数以及 Baker 收取的更换费用。
第二行包含 $n$ 个整数 $f_1, f_2, dots.h, f_n$ ($1 lt.eq.slant f_i lt.eq.slant m$)，其中 $f_i$ 表示第 $i$ 个节点上糖果的初始口味。
第三行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$ ($1 lt.eq.slant p_i lt.eq.slant n$)，其中 $p_i$ 是第 $i$ 个节点的父节点。
下一行包含 $m$ 个整数 $c_1, c_2, dots.h c_m$ ($1 lt.eq.slant c_i lt.eq.slant 10^2$)，其中 $c_i$ 表示更换一颗口味为 $i$ 的糖果的成本。
接下来的 $q$ 行描述查询。每行以一个整数 $t$ ($1 lt.eq.slant t lt.eq.slant 2$) 开头，表示查询类型。
若 $t = 1$，则该行描述第一类查询。随后有两个整数 $x$ 和 $w$ ($1 lt.eq.slant x lt.eq.slant n$, $1 lt.eq.slant w lt.eq.slant m$)，表示 Santa 将顶点 $x$ 上的糖果替换为口味 $w$。
否则，若 $t = 2$，该行描述第二类查询，随后有一个整数 $k$ ($1 lt.eq.slant k lt.eq.slant m$)，表示你需要输出给定口味 $k$ 的更换成本误差的期望值。
顶点编号从 $1$ 到 $n$。顶点 $1$ 是根节点。
对每个第二类查询，在单独一行输出答案。
你的答案若绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。
形式上，设你的答案为 $a$，标准答案为 $b$，评判程序仅在满足 $\frac{|a - b|}{max(1, b)} \leq 10^{-6}$ 时认为你的答案正确。
对于第 $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}$。
## Input
输入的第一行包含四个整数 $n$ ($2 lt.eq.slant n lt.eq.slant 5 dot.op 10^4$)、$m$、$q$、$C$ ($1 lt.eq.slant m, q lt.eq.slant 5 dot.op 10^4$, $0 lt.eq.slant C lt.eq.slant 10^6$) —— 分别表示节点数、糖果总口味数、查询数以及 Baker 收取的更换费用。第二行包含 $n$ 个整数 $f_1, f_2, dots.h, f_n$ ($1 lt.eq.slant f_i lt.eq.slant m$)，其中 $f_i$ 表示第 $i$ 个节点上糖果的初始口味。第三行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$ ($1 lt.eq.slant p_i lt.eq.slant n$)，其中 $p_i$ 是第 $i$ 个节点的父节点。下一行包含 $m$ 个整数 $c_1, c_2, dots.h c_m$ ($1 lt.eq.slant c_i lt.eq.slant 10^2$)，其中 $c_i$ 表示更换一颗口味为 $i$ 的糖果的成本。接下来的 $q$ 行描述查询。每行以一个整数 $t$ ($1 lt.eq.slant t lt.eq.slant 2$) 开头，表示查询类型。若 $t = 1$，则该行描述第一类查询。随后有两个整数 $x$ 和 $w$ ($1 lt.eq.slant x lt.eq.slant n$, $1 lt.eq.slant w lt.eq.slant m$)，表示 Santa 将顶点 $x$ 上的糖果替换为口味 $w$。否则，若 $t = 2$，该行描述第二类查询，随后有一个整数 $k$ ($1 lt.eq.slant k lt.eq.slant m$)，表示你需要输出给定口味 $k$ 的更换成本误差的期望值。顶点编号从 $1$ 到 $n$。顶点 $1$ 是根节点。
## Output
对每个第二类查询，在单独一行输出答案。你的答案若绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。形式上，设你的答案为 $a$，标准答案为 $b$，评判程序仅在满足 $\frac{|a - b|}{max(1, b)} \leq 10^{-6}$ 时认为你的答案正确。
[samples]
## Note
对于第 $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}$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of vertices in a rooted tree, with root at vertex $ 1 $.
Let $ m \in \mathbb{Z}^+ $ be the number of distinct candy flavours.
Let $ C \in \mathbb{R}_{\geq 0} $ be the fixed price charged by the Bakers per replacement.
Let $ c_k \in \mathbb{R}^+ $ be the cost to replace one candy of flavour $ k $, for $ k \in \{1, \dots, m\} $.
Let $ f: V \to \{1, \dots, m\} $ be the flavour assignment function, where $ f(i) $ is the flavour of the candy at vertex $ i $.
Let $ T $ be the rooted tree with parent array $ p $, defining the tree structure.
For any vertex $ x $, let $ S(x) \subseteq V $ denote the set of vertices in the subtree rooted at $ x $, and let $ |S(x)| $ be its size.
Let $ N_k(x) = |\{ v \in S(x) \mid f(v) = k \}| $ be the number of candies of flavour $ k $ in the subtree of $ x $.
**Constraints**
1. $ 2 \leq n \leq 5 \cdot 10^4 $, $ 1 \leq m, q \leq 5 \cdot 10^4 $, $ 0 \leq C \leq 10^6 $
2. $ 1 \leq f_i \leq m $ for all $ i \in \{1, \dots, n\} $
3. Parent of vertex $ i \geq 2 $ is $ p_i \in \{1, \dots, i-1\} $
4. $ 1 \leq c_k \leq 10^2 $ for all $ k \in \{1, \dots, m\} $
5. Queries:
- Type 1: Update $ f(x) \leftarrow w $ for $ x \in \{1, \dots, n\} $, $ w \in \{1, \dots, m\} $
- Type 2: Query expected error for flavour $ k \in \{1, \dots, m\} $
**Objective**
For each query of type 2 with flavour $ k $, compute the expected squared error:
$$
E(k) = \mathbb{E}\left[ \left( c_k \cdot N_k(x) - C \right)^2 \right]
$$
where $ x $ is chosen uniformly at random from the $ n $ vertices.
That is:
$$
E(k) = \frac{1}{n} \sum_{x=1}^{n} \left( c_k \cdot N_k(x) - C \right)^2
$$
**Operations**
- Type 1: Update $ f(x) \leftarrow w $, and propagate the change to all affected $ N_k(x) $ values.
- Type 2: Output $ E(k) $ as defined above.
API Response (JSON)
{
"problem": {
"name": "H. Santa's Gift",
"description": {
"content": "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$",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF960H"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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$...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Santa 有无限数量的每种 $m$ 种口味的糖果。你得到一棵包含 $n$ 个顶点的有根树。树的根是顶点 $1$。每个顶点恰好包含一颗糖果。第 $i$ 个顶点的糖果口味为 $f_i$。\n\n有时 Santa 担心口味为 $k$ 的糖果融化了。他随机选择任意一个顶点 $x$，并将 $x$ 的子树发送给 Baker 进行更换。在更换过程中，所有口味为 $k$ 的糖果都会被替换为同一种新口味的糖果，而其他...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices in a rooted tree, with root at vertex $ 1 $. \nLet $ m \\in \\mathbb{Z}^+ $ be the number of distinct candy flavours. \nLet $ C \\in...",
"is_translate": false,
"language": "Formal"
}
]
}