分数: 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