CF960H Santa's Gift

圣诞老人拥有每种口味 $m$ 的无限糖果。给定一棵包含 $n$ 个顶点的有根树，根节点为顶点 $1$。每个顶点恰好包含一颗糖果，第 $i$ 个顶点的糖果口味为 $f_i$。 有时圣诞老人担心口味 $k$ 的糖果可能融化。他会随机选择一个顶点 $x$，并将 $x$ 的子树交给面包师进行替换。在替换过程中，所有口味 $k$ 的糖果会被替换为同口味的新糖果，其他口味的糖果保持不变。替换完成后，树会恢复原状。 替换一颗口味 $k$ 糖果的实际成本为 $c_k$（每个 $k$ 给定）。面包师为简化计算保持固定收费价格 $C$。每次子树进行替换时，无论子树大小或口味如何，面包师都收取 $C$ 的费用。 假设对于给定口味 $k$，圣诞老人选择替换顶点的概率在所有顶点中均匀分布。你需要计算口味 $k$ 替换成本计算误差的期望值。误差定义如下： $$ E(k) = (\text{实际成本} - \text{面包师收取价格})^2 $$ 注意实际成本等于单颗口味 $k$ 糖果替换成本乘以子树中该口味糖果数量。 此外，圣诞老人可能希望用口袋中的糖果替换顶点 $x$ 处的糖果。你需要处理两种操作： - 将顶点 $x$ 的糖果口味改为 $w$ - 计算给定口味 $k$ 替换成本误差的期望值

无

无

对于第一个询问，当选择顶点 $1$、$2$ 或 $3$ 时，口味 $1$ 的替换误差分别为 $66^2$、$66^2$ 和 $(-7)^2$。由于选择概率均等，期望值为 $\frac{66^2 + 66^2 + (-7)^2}{3}$。 类似地，第二个询问的期望值为 $\frac{41^2 + (-7)^2 + (-7)^2}{3}$。 第三个询问后，顶点 $2$ 的口味从 $1$ 变为 $3$。 第四个询问的期望值为 $\frac{(-7)^2 + (-7)^2 + (-7)^2}{3}$。 第五个询问的期望值为 $\frac{89^2 + 41^2 + (-7)^2}{3}$。 翻译由 DeepSeek R1 完成