{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003cfont color\u003d\"#000\"\u003e问题 F:\u003c/font\u003e \u003c/h1\u003e\n\n\u003cp\u003e\n给定一棵包含 \u003ci\u003eN\u003c/i\u003e 个节点的树 \u003ci\u003eT\u003c/i\u003e。每个节点从 1 到 \u003ci\u003eN\u003c/i\u003e 编号,节点 1 总是树 \u003ci\u003eT\u003c/i\u003e 的根节点。考虑以下两种对树 \u003ci\u003eT\u003c/i\u003e 的操作:\n\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e\u003cspan\u003eM v\u003c/span\u003e: (标记) 标记节点 \u003cspan\u003ev\u003c/span\u003e。\u003c/li\u003e\n \u003cli\u003e\u003cspan\u003eQ v\u003c/span\u003e: (查询) 打印节点 \u003cspan\u003ev\u003c/span\u003e 的最近标记祖先的索引,该祖先离节点 \u003cspan\u003ev\u003c/span\u003e 最近。初始时,只有根节点被标记。注意节点本身也是其祖先。\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\n你的任务是编写一个程序,在给定树上执行一系列这些操作,并计算每个 Q 操作将打印的值。为避免输出文件过大,要求你的程序打印所有查询操作输出的总和。评测人员确认可以在给定序列中计算每个查询操作的输出。\n\u003c/p\u003e\n\n\u003ch2\u003e输入\u003c/h2\u003e\n\n\u003cp\u003e\n输入包含多个数据集。每个数据集的格式如下:\n\u003c/p\u003e\n\n\u003cp\u003e\n输入的第一行包含两个整数 \u003ci\u003eN\u003c/i\u003e 和 \u003ci\u003eQ\u003c/i\u003e,表示树 \u003ci\u003eT\u003c/i\u003e 中节点的数量和操作的数量。这些数字满足以下条件:1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100000,1 ≤ \u003ci\u003eQ\u003c/i\u003e ≤ 100000。\n\u003c/p\u003e\n\u003cp\u003e\n接下来的 \u003ci\u003eN\u003c/i\u003e - 1 行描述树 \u003ci\u003eT\u003c/i\u003e 的配置。每行包含一个整数 \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e (\u003ci\u003ei\u003c/i\u003e \u003d 2, ... , \u003ci\u003eN\u003c/i\u003e),表示第 \u003ci\u003ei\u003c/i\u003e 个节点的父节点的索引。\n\u003c/p\u003e\n\u003cp\u003e\n接下来的 \u003ci\u003eQ\u003c/i\u003e 行按顺序包含操作。每个操作格式为 \"\u003cspan\u003eM v\u003c/span\u003e\" 或 \"\u003cspan\u003eQ v\u003c/span\u003e\",其中 \u003ci\u003ev\u003c/i\u003e 是一个节点的索引。\n\u003c/p\u003e\n\n\u003cp\u003e\n最后一个数据集后面是一行包含两个零。这一行不属于任何数据集,不应被处理。\n\u003c/p\u003e\n\n\n\u003ch2\u003e输出\u003c/h2\u003e\n\n\u003cp\u003e\n对于每个数据集,将所有查询操作的输出总和打印在一行中。\n\u003c/p\u003e\n\n\u003ch2\u003e样例输入\u003c/h2\u003e\n\u003cpre\u003e6 3\n1\n1\n2\n3\n3\nQ 5\nM 3\nQ 5\n0 0\n\u003c/pre\u003e\n\n\u003ch2\u003e样例输入对应的输出\u003c/h2\u003e\n\u003cpre\u003e4\n\u003c/pre\u003e"}}]}