当前没有测试数据。

G - 最小可达城市

得分：600 分

题目描述

我们有一个有 $N$ 个编号为 $1$ 到 $N$ 的顶点的有向图 $G_S$，它有 $N-1$ 条边。第 $i$ 条边 $(1 \leq i \leq N-1)$ 从顶点 $p_i\ (1 \leq p_i \leq i)$ 指向顶点 $i+1$。

我们有另一个有 $N$ 个编号为 $1$ 到 $N$ 的顶点的有向图 $G$，起始时 $G$ 等于 $G_S$。 按照给定的顺序对 $G$ 进行 $Q$ 个查询。查询有以下两种类型：

• 1 u v：在 $G$ 中添加一条从顶点 $u$ 到顶点 $v$ 的边。 保证满足以下条件：
  • $u \neq v$。
  • 在 $G_S$ 中，通过某些边，顶点 $u$ 可以从顶点 $v$ 到达。
• 2 x：输出从顶点 $x$ 经过一些边在 $G$ 中可达的顶点中编号最小的顶点（包括顶点 $x$）。

限制

• $2\leq N \leq 2\times 10^5$
• $1\leq Q \leq 2\times 10^5$
• $1\leq p_i\leq i$
• 对于第一种格式的每个查询：
  • $1\leq u,v \leq N$。
  • $u \neq v$。
  • 在 $G_S$ 中，通过某些边，顶点 $u$ 可以从顶点 $v$ 到达。
• 对于第二种格式的每个查询，$1\leq x \leq N$。
• 输入中的所有值都为整数。

输入

输入以如下格式从标准输入中给出：

$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 ```

输出

输出 $q$ 行，其中 $q$ 是第二种格式的查询数。 第 $j$ 行 $(1\leq j \leq q)$ 应包含第 $j$ 个查询的答案（第二种格式）。