← 返回题目列表

AtCoder · abc295_g

G. 最低可达城市

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一个有向图 G_S 与 N 顶点编号 1 to N。 它有 N-1 边缘。的 i第边缘 (1\leq i \leq N-1) 从顶点出发 p_i\ (1\leq p_i \leq i) 到顶点 i+1.

我们有另一个有向图 G 与 N 顶点编号 1 to N。 最初, G 等于 G_S。 工艺流程 Q 查询 G 按照给出的顺序。查询有以下两种。

  • 1 u v :添加一条边 G 从顶点出发 u 到顶点 v。 保证满足以下条件。
    • u \neq v.
    • On 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.
    • On 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-th 查询,采用以下格式之一:

1 u v
2 x

输出

打印 q 行,其中 q 是第二种格式的查询数。 的 i第行 (1\leq j \leq q) 应包含以下问题的答案 j第二种格式的第一个查询。


示例输入 1

5
1 2 3 3
5
2 4
1 4 2
2 4
1 5 1
2 4

示例输出 1

4
2
1
  • 第一次查询时,只有顶点 4 可从顶点到达 4 通过一些边缘 G.
  • 第三次查询时,顶点 2, 3, 4,和 5 可从顶点到达 4 通过一些边缘 G.
  • 第五次查询时,顶点 1, 2, 3, 4,和 5 可从顶点到达 4 通过一些边缘 G.

示例输入 2

7
1 1 2 2 3 3
10
2 5
1 5 2
2 5
1 2 1
1 7 1
1 6 3
2 5
2 6
2 1
1 7 1

示例输出 2

5
2
1
1
1