← 返回题目列表

Codeforces · 960/H

H. 圣诞老人的礼物

中文机器翻译题面 查看原题

圣诞老人对于每种 $$$m$$$ 口味都有无限数量的糖果。给你一棵有 $$$n$$$ 个顶点的有根树。树的根是顶点$$$1$$$。每个顶点恰好包含一颗糖果。第 $$$i$$$ 个顶点有 $$$f_i$$$ 口味的糖果。

有时圣诞老人担心 $$$k$$$ 口味的糖果融化了。他随机选择任意顶点 $$$x$$$ 并将 $$$x$$$ 的子树发送给 Bakers 进行替换。在替换中,所有口味为 $$$k$$$ 的糖果都被替换为相同口味的新糖果。没有味道的糖果 $$$k$$$ 保持不变。更换后,树就恢复了。

更换一颗 $$$k$$$ 口味糖果的实际成本为 $$$c_k$$$(针对每个 $$$k$$$ 给出)。面包师保持价格固定以便计算简单。每次当子树需要替换时,面包师都会收取 $$$C$$$ 费用,无论它是哪一个子树以及它是什么口味。

假设对于给定的风味$$$k$$$,圣诞老人选择一个顶点进行替换的概率对于所有顶点来说都是相同的。您需要找出计算更换风味 $$$k$$$ 的成本时的预期误差值。计算成本的误差定义如下。

$$$$$$ 误差\ E(k) =\ (实际成本\ –\ 价格\ 由\ 面包师收取) ^ 2.$$$$$$

请注意,实际成本是更换一颗 $$$k$$$ 口味糖果的成本乘以子树中糖果的数量。

另外,有时圣诞老人可能希望用口袋里的某种口味的糖果替换顶点 $$$x$$$ 处的糖果。

您需要处理两种类型的操作:

- 将顶点 $$$x$$$ 处的糖果口味更改为 $$$w$$$。
- 计算给定口味 $$$k$$$ 的更换成本时的预期误差值。

输入

输入的第一行包含四个整数 $$$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$$$) — 分别是节点数量、不同口味糖果的总数、查询数量和面包师更换的价格。

第二行包含 $$$n$$$ 整数 $$$f_1, f_2, \dots, f_n$$$ ($$$1 \leqslant f_i \leqslant m$$$),其中 $$$f_i$$$ 是第 $$$i$$$ 节点中糖果的初始口味。

第三行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \leqslant p_i \leqslant n$$$),其中 $$$p_i$$$ 是第 $$$i$$$ 个节点的父节点。

下一行包含 $$$m$$$ 整数 $$$c_1, c_2, \dots c_m$$$ ($$$1 \leqslant c_i \leqslant 10^2$$$),其中 $$$c_i$$$ 是更换一颗 $$$i$$$ 口味糖果的成本。

接下来的 $$$q$$$ 行描述查询。每行以整数 $$$t$$$ 开头 ($$$1 \leqslant t \leqslant 2$$$) — 查询的类型。

如果$$$t = 1$$$,则该行描述第一种类型的查询。后面跟着两个整数 $$$x$$$ 和 $$$w$$$ ($$$1 \leqslant x \leqslant n$$$, $$$1 \leqslant w \leqslant m$$$),这意味着圣诞老人将顶点 $$$x$$$ 处的糖果替换为风味 $$$w$$$。

否则,如果 $$$t = 2$$$,该行描述了第二种类型的查询,并且后面跟着一个整数 $$$k$$$ ($$$1 \leqslant k \leqslant m$$$),这意味着您应该在计算给定风味 $$$k$$$ 的替换成本时打印错误的预期值。

顶点索引从 $$$1$$$ 到 $$$n$$$。顶点 $$$1$$$ 是根。

输出

在单独的行中输出第二类型的每个查询的答案。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\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

注意

对于 $$$1$$$-st 查询,如果选择顶点 $$$1$$$、$$$2$$$ 或 $$$3$$$,则计算风味 $$$1$$$ 的替换成本时的错误分别为 $$$66^2$$$、$$$66^2$$$ 和 $$$(-7)^2$$$。由于选择任意顶点的概率相同,因此误差的期望值为$$$\frac{66^2+66^2+(-7)^2}{3}$$$。

同样,对于 $$$2$$$-nd 查询,错误的预期值为 $$$\frac{41^2+(-7)^2+(-7)^2}{3}$$$。

在 $$$3$$$-rd 查询之后,顶点 $$$2$$$ 处的风味从 $$$1$$$ 变为 $$$3$$$。

对于第 $$$4$$$ 个查询,错误的预期值为 $$$\frac{(-7)^2+(-7)^2+(-7)^2}{3}$$$。

同样,对于第 $$$5$$$ 个查询,错误的预期值为 $$$\frac{89^2+41^2+(-7)^2}{3}$$$。