成熟时追随原神

可莉生活在一颗有根树上，初始节点从 $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$ 次修改之间不独立，但是蒙德人每次修建的新道路不受上一次结果的影响。 ## Input 第一行，一个整数 $n$，表示初始树的大小。 第二行至第 $n$ 行，每行输入一个整数，第 $i$ 行将给出 $f_i$，即初始树中 $i$ 的父节点。初始时，节点 $1$ 为树根。 第 $n+1$ 行，一个整数 $m$，表示修改操作个数。 第 $n+2$ 行至第 $n+m+1$ 行，每行输入一个修改操作，形式见 **题目描述**。 ## Output 输出共 $m+1$ 行。 第 $1$ 行，为初始时的答案。 第 $2$ 行至第 $m+1$ 行，第 $i$ 行应输出第 $i-1$ 次修改操作后的答案。 所有输出均对 $998244353$ 取模。具体而言，如果答案为 $\frac{p}{q}$，你应当输出一个满足 $xq\equiv p\pmod {998244353}$ 的 $x$。 [samples] ## Background 可莉喜欢生活在树上。  画师 pid：4787895 ## Note $$ \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<i$。