P8882 成熟时追随原神

可莉喜欢生活在树上。  画师 pid：4787895

可莉生活在一颗有根树上，初始节点从 $1$ 到 $n$ 编号。为了方便可莉的出行，蒙德人决定从每个非叶子节点出发，修建一条新道路。具体而言，对与每个非叶子节点 $u$，蒙德人会从其子节点中均匀随机选取一个点 $v$，并在 $u$ 和 $v$ 之间修建一条新道路。显然，这些新修建的道路连成了许多的连通块。为了帮助他们的修建，你需要告诉蒙德人，连通块个数的期望是多少。 可莉听说这个任务后，认为它对于你而言太简单了。因此，她决定添加一些对于树的修改操作： - $\text{Add}\ u$：在节点 $u$ 下添加一子结点，编号为 $n+i$，其中 $i$ 为操作编号。保证操作前结点 $u$ 存在。 - $\text{Del}\ u$：删除结点 $u$。保证操作前结点 $u$ 存在且为叶子结点。 - $\text{Upd}\ u$：将树根变为 $u$。保证操作前结点 $u$ 存在。 同时，对于任意时刻，保证树不会被删空。 对于初始的树和每次修改之后所得的树，你都需要回答一遍上述的问题。注意，$m$ 次修改之间不独立，但是蒙德人每次修建的新道路不受上一次结果的影响。

无

无

$$ \begin{array}{|c|c|c|c|}\hline \textbf{测试点编号}& { n\le} & {m\le} & \textbf{特殊性质} \cr\hline 1\sim 3 & 5 & 5 & - \cr\hline 4\sim 7 & 1000 & 1000 &- \cr\hline 8\sim 10 & 10^5 & 0 & - \cr\hline 11\sim 13 & 10^5 & 2\times 10^5 & \textbf{AB}\cr\hline 14\sim 16 & 2\times 10^5 & 5\times 10^4 & \textbf{A} \cr\hline 17\sim 20 & 2\times 10^5 & 2\times 10^5 & - \cr\hline \end{array} $$ - 特殊性质 $\textbf{A}$：保证不存在 $\text{Upd}$ 操作。 - 特殊性质 $\textbf{B}$：保证不存在 $\text{Del}$ 操作。 对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$。保证 $1\le f_i