A11724. 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. $$ </p><p>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.</p><p>Also, sometimes Santa may wish to replace a candy at vertex $x$ with a candy of some flavour from his pocket.</p><p>You need to handle two types of operations: </p><ul> <li> Change the flavour of the candy at vertex $x$ to $w$ . </li><li> Calculate the expected value of error in calculating the cost of replacement for a given flavour $k$$$.
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. $$ </p><p>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.</p><p>Also, sometimes Santa may wish to replace a candy at vertex $x$ with a candy of some flavour from his pocket.</p><p>You need to handle two types of operations: </p><ul> <li> Change the flavour of the candy at vertex $x$ to $w$ . </li><li> Calculate the expected value of error in calculating the cost of replacement for a given flavour $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.
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 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}$ .
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}$ .
输入输出样例
输入 #1
3 5 5 7 3 1 4 1 1 73 1 48 85 89 2 1 2 3 1 2 3 2 1 2 3
输出 #1
2920.333333333333 593.000000000000 49.000000000000 3217.000000000000
说明/提示
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}$ .
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}$ .