Santa's Gift

题意翻译

给一棵$n$个点的有根树，每个点有一个颜色$a_i$，对于每种颜色有一个权值$b_i$。再给你一个常数$C$。 共进行$Q$次操作，操作分为两种： - ```1 x y```把节点x的颜色修改为y - ```2 x```对颜色x进行询问。求$\frac{\sum_{i=1}^n(S_i\times b_x-C)^2}{n}$，其中$S_i$是$i$的子树中，颜色=x的点的个数。 $2\leq n\leq 50000$,$1\leq m,Q\leq 50000$ $1\leq a_1,a_2,...,a_n\leq m$ $1\leq b_1,b_2,...,b_m\leq 100$

题目描述

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

输入输出格式

输入格式

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

输入输出样例

输入样例 #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} $ .

题意翻译

- 给出一棵 $n$ 个节点的有根树，根为 $1$。点 $2\sim n$ 的父亲为 $p_2\sim p_n$。有 $m$ 种颜色。点 $i$ 的颜色为 $f_i$，颜色 $i$ 的权值为 $c_i$。有两种操作共 $q$ 次： - $\texttt{1 }x\text{ }y$，将 $f_x\leftarrow y$。 - $\texttt{2 }x$，从树中等概率选取一个点 $i$，得到 $(S_i\times b_x-C)^2$ 的价值。求期望价值。其中 $S_i$ 表示以 $i$ 为根的子树中颜色为 $x$ 的节点数。$C$ 是给定的常数。 **输入格式** - 第一行四个自然数 $n,m,q,C$（$2\le n\le 5\times 10^4$，$1\le m,q\le 5\times 10^4$，$0\le C\le 10^6$）。 - 第二行 $n$ 个正整数 $f_1\sim f_n$（$1\le f_i\le m$）。 - 第三行 $n-1$ 个正整数为 $p_2\sim p_n$（$1\le p_i\le n$）。 - 第四行 $m$ 个正整数 $b_1\sim b_m$（$1\le c_i\le 100$）。 - 接下来 $q$ 行每行为一个操作 $\texttt{1 }x\text{ }y$ 或 $\texttt{2 }x$。 **输出格式** 对于 $\texttt{2}$ 操作，输出期望。