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$.

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 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} $ .

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} $ .