AT_abc295_g.[ABC295G] Minimum Reachable City

有一个包含 $N$ 个顶点的有向图 $G_S$，顶点编号为 $1$ 到 $N$。$G_S$ 有 $N-1$ 条边，第 $i$ 条边（$1\leq i\leq N-1$）是从顶点 $p_i$（$1\leq p_i\leq i$）指向顶点 $i+1$。

有一个包含 $N$ 个顶点的有向图 $G$，顶点编号为 $1$ 到 $N$。最初，$G$ 与 $G_S$ 完全相同。现在有 $Q$ 个关于 $G$ 的操作，请按给定顺序依次处理。操作有以下两种类型：

• 1 u v ：在 $G$ 中添加一条从顶点 $u$ 到顶点 $v$ 的有向边。保证满足以下条件：
  • $u\neq v$
  • 在 $G_S$ 上，从顶点 $v$ 沿若干条边可以到达顶点 $u$
• 2 x ：输出在 $G$ 上，从顶点 $x$ 沿若干条边可以到达的所有顶点（包括 $x$）中，编号最小的顶点编号。

输入通过标准输入给出，格式如下：

$N$

$p_1$ $p_2$ $\dots$ $p_{N-1}$

$Q$

$\mathrm{query}_1$

$\mathrm{query}_2$

$\vdots$

$\mathrm{query}_Q$

其中，$\mathrm{query}_i$ 表示第 $i$ 个操作，格式如下之一：

$1$ $u$ $v$

$2$ $x$

设第 $2$ 类操作的次数为 $q$，请输出 $q$ 行。第 $j$ 行（$1\leq j\leq q$）输出第 $j$ 个 $2$ 类操作的答案。

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq Q\leq 2\times 10^5$
• $1\leq p_i\leq i$
• 对于第 $1$ 类操作：
  • $1\leq u,v\leq N$
  • $u\neq v$
  • 在 $G_S$ 上，从顶点 $v$ 沿若干条边可以到达顶点 $u$
• 对于第 $2$ 类操作，$1\leq x\leq N$
• 所有输入均为整数

样例解释 1

• 在第 $1$ 个操作时，从顶点 $4$ 出发在 $G$ 上能够到达的顶点只有 $4$。
• 在第 $3$ 个操作时，从顶点 $4$ 出发在 $G$ 上能够到达的顶点为 $2,3,4,5$。
• 在第 $5$ 个操作时，从顶点 $4$ 出发在 $G$ 上能够到达的顶点为 $1,2,3,4,5$。

由 ChatGPT 4.1 翻译