{"raw_statement":[{"iden":"statement","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$\\-th vertex has a candy of flavour $f_i$.\n\nSometimes 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.\n\nThe _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.\n\nSuppose 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.\n\nError\\\\ E(k) =\\\\ (Actual Cost\\\\ –\\\\ Price\\\\ charged\\\\ by\\\\ the\\\\ Bakers) ^ 2.\n\nNote 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.\n\nAlso, sometimes Santa may wish to replace a candy at vertex $x$ with a candy of some flavour from his pocket.\n\nYou need to handle two types of operations:\n\n*   Change the flavour of the candy at vertex $x$ to $w$.\n*   Calculate the expected value of error in calculating the cost of replacement for a given flavour $k$."},{"iden":"input","content":"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.\n\nThe 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.\n\nThe 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.\n\nThe 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$.\n\nThe next $q$ lines describe the queries. Each line starts with an integer $t$ ($1 \\leqslant t \\leqslant 2$) — the type of the query.\n\nIf $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$.\n\nOtherwise, 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$.\n\nThe vertices are indexed from $1$ to $n$. Vertex $1$ is the root."},{"iden":"output","content":"Output the answer to each query of the second type in a separate line.\n\nYour answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.\n\nFormally, 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}$."},{"iden":"example","content":"Input\n\n3 5 5 7\n3 1 4\n1 1\n73 1 48 85 89\n2 1\n2 3\n1 2 3\n2 1\n2 3\n\nOutput\n\n2920.333333333333\n593.000000000000\n49.000000000000\n3217.000000000000"},{"iden":"note","content":"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}$.\n\nSimilarly, for $2$\\-nd query the expected value of error is $\\frac{41^2+(-7)^2+(-7)^2}{3}$.\n\nAfter $3$\\-rd query, the flavour at vertex $2$ changes from $1$ to $3$.\n\nFor $4$\\-th query, the expected value of error is $\\frac{(-7)^2+(-7)^2+(-7)^2}{3}$.\n\nSimilarly, for $5$\\-th query, the expected value of error is $\\frac{89^2+41^2+(-7)^2}{3}$."}],"translated_statement":[{"iden":"statement","content":"Santa 有无限数量的每种 $m$ 种口味的糖果。你得到一棵包含 $n$ 个顶点的有根树。树的根是顶点 $1$。每个顶点恰好包含一颗糖果。第 $i$ 个顶点的糖果口味为 $f_i$。\n\n有时 Santa 担心口味为 $k$ 的糖果融化了。他随机选择任意一个顶点 $x$，并将 $x$ 的子树发送给 Baker 进行更换。在更换过程中，所有口味为 $k$ 的糖果都会被替换为同一种新口味的糖果，而其他非 $k$ 口味的糖果保持不变。更换完成后，树被恢复。\n\n更换一颗口味为 $k$ 的糖果的 _实际_ 成本为 $c_k$（每个 $k$ 均给出）。Baker 为简化计算而固定价格。每当有子树前来更换时，Baker 都会收取固定费用 $C$，无论子树是哪个、口味是哪种。\n\n假设对于给定的口味 $k$，Santa 选择任一顶点进行更换的概率均等。你需要计算计算口味 $k$ 更换成本的 _误差_ 的期望值。误差定义如下：\n\n$$ Error\\ E(k) =\\ (实际成本\\ –\\ Baker 收取的价格) ^ 2.$$\n\n注意，实际成本是更换一颗口味为 $k$ 的糖果的成本乘以子树中糖果的数量。\n\n此外，有时 Santa 可能希望用他口袋中某种口味的糖果替换顶点 $x$ 上的糖果。\n\n你需要处理两种操作：\n\n输入的第一行包含四个整数 $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\n第二行包含 $n$ 个整数 $f_1, f_2, dots.h, f_n$ ($1 lt.eq.slant f_i lt.eq.slant m$)，其中 $f_i$ 表示第 $i$ 个节点上糖果的初始口味。\n\n第三行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$ ($1 lt.eq.slant p_i lt.eq.slant n$)，其中 $p_i$ 是第 $i$ 个节点的父节点。\n\n下一行包含 $m$ 个整数 $c_1, c_2, dots.h c_m$ ($1 lt.eq.slant c_i lt.eq.slant 10^2$)，其中 $c_i$ 表示更换一颗口味为 $i$ 的糖果的成本。\n\n接下来的 $q$ 行描述查询。每行以一个整数 $t$ ($1  lt.eq.slant  t  lt.eq.slant  2$) 开头，表示查询类型。\n\n若 $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$。\n\n否则，若 $t = 2$，该行描述第二类查询，随后有一个整数 $k$ ($1  lt.eq.slant  k  lt.eq.slant  m$)，表示你需要输出给定口味 $k$ 的更换成本误差的期望值。\n\n顶点编号从 $1$ 到 $n$。顶点 $1$ 是根节点。\n\n对每个第二类查询，在单独一行输出答案。\n\n你的答案若绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。\n\n形式上，设你的答案为 $a$，标准答案为 $b$，评判程序仅在满足 $\\frac{|a - b|}{max(1, b)} \\leq 10^{-6}$ 时认为你的答案正确。\n\n对于第 $1$ 个查询，若选择顶点 $1$、$2$ 或 $3$，口味 $1$ 的更换成本误差分别为 $66^2$、$66^2$ 和 $(-7)^2$。由于选择任一顶点的概率相同，因此误差的期望值为 $\\frac{66^2 + 66^2 + (-7)^2}{3}$。\n\n类似地，对于第 $2$ 个查询，误差的期望值为 $\\frac{41^2 + (-7)^2 + (-7)^2}{3}$。\n\n在第 $3$ 个查询后，顶点 $2$ 上的糖果口味由 $1$ 变为 $3$。\n\n对于第 $4$ 个查询，误差的期望值为 $\\frac{(-7)^2 + (-7)^2 + (-7)^2}{3}$。\n\n类似地，对于第 $5$ 个查询，误差的期望值为 $\\frac{89^2 + 41^2 + (-7)^2}{3}$。"},{"iden":"input","content":"输入的第一行包含四个整数 $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$ 是根节点。"},{"iden":"output","content":"对每个第二类查询，在单独一行输出答案。你的答案若绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。形式上，设你的答案为 $a$，标准答案为 $b$，评判程序仅在满足 $\\frac{|a - b|}{max(1, b)} \\leq 10^{-6}$ 时认为你的答案正确。"},{"iden":"note","content":"对于第 $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}$。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 \\mathbb{R}_{\\geq 0} $ be the fixed price charged by the Bakers per replacement.  \nLet $ c_k \\in \\mathbb{R}^+ $ be the cost to replace one candy of flavour $ k $, for $ k \\in \\{1, \\dots, m\\} $.  \nLet $ f: V \\to \\{1, \\dots, m\\} $ be the flavour assignment function, where $ f(i) $ is the flavour of the candy at vertex $ i $.  \nLet $ T $ be the rooted tree with parent array $ p $, defining the tree structure.  \nFor 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.  \nLet $ N_k(x) = |\\{ v \\in S(x) \\mid f(v) = k \\}| $ be the number of candies of flavour $ k $ in the subtree of $ x $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 5 \\cdot 10^4 $, $ 1 \\leq m, q \\leq 5 \\cdot 10^4 $, $ 0 \\leq C \\leq 10^6 $  \n2. $ 1 \\leq f_i \\leq m $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. Parent of vertex $ i \\geq 2 $ is $ p_i \\in \\{1, \\dots, i-1\\} $  \n4. $ 1 \\leq c_k \\leq 10^2 $ for all $ k \\in \\{1, \\dots, m\\} $  \n5. Queries:  \n   - Type 1: Update $ f(x) \\leftarrow w $ for $ x \\in \\{1, \\dots, n\\} $, $ w \\in \\{1, \\dots, m\\} $  \n   - Type 2: Query expected error for flavour $ k \\in \\{1, \\dots, m\\} $\n\n**Objective**  \nFor each query of type 2 with flavour $ k $, compute the expected squared error:  \n$$\nE(k) = \\mathbb{E}\\left[ \\left( c_k \\cdot N_k(x) - C \\right)^2 \\right]\n$$  \nwhere $ x $ is chosen uniformly at random from the $ n $ vertices.  \n\nThat is:  \n$$\nE(k) = \\frac{1}{n} \\sum_{x=1}^{n} \\left( c_k \\cdot N_k(x) - C \\right)^2\n$$  \n\n**Operations**  \n- Type 1: Update $ f(x) \\leftarrow w $, and propagate the change to all affected $ N_k(x) $ values.  \n- Type 2: Output $ E(k) $ as defined above.","simple_statement":null,"has_page_source":false}