{"raw_statement":[{"iden":"background","content":"可莉喜欢生活在树上。\n\n![](https://img2.huashi6.com/images/resource/2021/04/29/8945867h9p0.jpg?imageMogr2/quality/100/interlace/1/thumbnail/700x)\n\n画师 pid：4787895"},{"iden":"statement","content":"可莉生活在一颗有根树上，初始节点从 $1$ 到 $n$ 编号。为了方便可莉的出行，蒙德人决定从每个非叶子节点出发，修建一条新道路。具体而言，对与每个非叶子节点 $u$，蒙德人会从其子节点中均匀随机选取一个点 $v$，并在 $u$ 和 $v$ 之间修建一条新道路。显然，这些新修建的道路连成了许多的连通块。为了帮助他们的修建，你需要告诉蒙德人，连通块个数的期望是多少。\n\n可莉听说这个任务后，认为它对于你而言太简单了。因此，她决定添加一些对于树的修改操作：\n\n- $\\text{Add}\\ u$：在节点 $u$ 下添加一子结点，编号为 $n+i$，其中 $i$ 为操作编号。保证操作前结点 $u$ 存在。\n- $\\text{Del}\\ u$：删除结点 $u$。保证操作前结点 $u$ 存在且为叶子结点。\n- $\\text{Upd}\\ u$：将树根变为 $u$。保证操作前结点 $u$ 存在。\n\n同时，对于任意时刻，保证树不会被删空。\n\n对于初始的树和每次修改之后所得的树，你都需要回答一遍上述的问题。注意，$m$ 次修改之间不独立，但是蒙德人每次修建的新道路不受上一次结果的影响。"},{"iden":"input","content":"第一行，一个整数 $n$，表示初始树的大小。\n\n第二行至第 $n$ 行，每行输入一个整数，第 $i$ 行将给出 $f_i$，即初始树中 $i$ 的父节点。初始时，节点 $1$ 为树根。\n\n第 $n+1$ 行，一个整数 $m$，表示修改操作个数。\n\n第 $n+2$ 行至第 $n+m+1$ 行，每行输入一个修改操作，形式见 **题目描述**。"},{"iden":"output","content":"输出共 $m+1$ 行。\n\n第 $1$ 行，为初始时的答案。\n\n第 $2$ 行至第 $m+1$ 行，第 $i$ 行应输出第 $i-1$ 次修改操作后的答案。\n\n所有输出均对 $998244353$ 取模。具体而言，如果答案为 $\\frac{p}{q}$，你应当输出一个满足 $xq\\equiv p\\pmod {998244353}$ 的 $x$。"},{"iden":"note","content":"$$\n\\begin{array}{|c|c|c|c|}\\hline\n\\textbf{测试点编号}& { n\\le} & {m\\le} & \\textbf{特殊性质} \\cr\\hline\n1\\sim 3 & 5 & 5 & - \\cr\\hline\n4\\sim 7 & 1000 & 1000 &- \\cr\\hline\n8\\sim 10 & 10^5 & 0 & - \\cr\\hline\n11\\sim 13 & 10^5 & 2\\times 10^5 & \\textbf{AB}\\cr\\hline\n14\\sim 16 & 2\\times 10^5 & 5\\times 10^4 & \\textbf{A} \\cr\\hline\n17\\sim 20 & 2\\times 10^5 & 2\\times 10^5 & - \\cr\\hline\n\\end{array}\n$$\n\n- 特殊性质 $\\textbf{A}$：保证不存在 $\\text{Upd}$ 操作。\n- 特殊性质 $\\textbf{B}$：保证不存在 $\\text{Del}$ 操作。\n\n对于 $100\\%$ 的数据，$1\\le n,m\\le 2\\times 10^5$。保证 $1\\le f_i<i$。"}],"translated_statement":null,"sample_group":[["2\n1\n4\nAdd 1\nUpd 2\nDel 3\nDel 1","1\n2\n1\n1\n1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}