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 翻译