CF68D Half-decay tree

最近 Petya 对物理产生了浓厚的兴趣。Anna V. 老师注意到了 Petya 的兴趣，并给了他一个有趣的物理难题 —— “半衰树”。 一棵半衰树是高度为 $h$ 的完美二叉树。树的高度定义为从根节点到任意叶子节点的简单路径上的边数。在研究这棵树的过程中，Petya 可以向顶点添加电子，或用同步加速器激发发生“随机衰变”。随机衰变指的是随机选择从根到某个叶子的路径，并删除这条路径上的所有边（每个叶子被选中的概率都相同）。每次衰变后，Petya 会把被删除的边重新加入树中（即，树会恢复原状）。 被分解后，树裂解为若干连通分量。每个分量的“电荷”定义为该分量所有顶点上电子的总和。整棵分解后的树的“电势”是所有连通分量的电荷的最大值。每次随机衰变前，Petya 都很好奇分解后树的电势的数学期望是多少。

第一行包含两个整数 $h$ 和 $q$（$1 \leq h \leq 30, 1 \leq q \leq 10^5$）。接下来的 $q$ 行，每行包含以下两种操作之一： - `add v e`：Petya 向编号为 $v$ 的顶点添加 $e$ 个电子（$1 \leq v \leq 2^{h+1}-1, \, 0 \leq e \leq 10^4$）。其中 $v$ 和 $e$ 为整数。 树中顶点的编号方式如下：根节点编号为 1，任意节点 $x$ 的左右孩子分别编号为 $2x$ 和 $2x+1$。 - `decay`：Petya 进行一次衰变操作。

对于每个 decay 操作，请输出分解后树的电势的数学期望。答案的绝对误差或相对误差不超过 $10^{-4}$。

由 ChatGPT 5 翻译