Minimum Reachable City

题目描述

我们有一个有向图 $G_S$，有 $N$ 个顶点，编号为 $1$ 到 $N$。 它有 $N-1$ 条边。第 $i$ 条边 $(1\leq i \leq N-1)$ 从顶点 $p_i\ (1\leq p_i \leq i)$ 指向顶点 $i+1$。 我们有另一个有向图 $G$，有 $N$ 个顶点，编号为 $1$ 到 $N$。 最初，$G$ 等于 $G_S$。 按给定顺序对 $G$ 处理 $Q$ 个查询。查询有两种类型如下。

$1 u v$ ：向 $G$ 中添加一条从顶点 $u$ 到顶点 $v$ 的边。 保证满足以下条件。 $u \neq v$。 在 $G_S$ 上，顶点 $u$ 可通过若干条边从顶点 $v$ 到达。

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

输出格式

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

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

4
2
1

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

5
2
1
1
1

提示

$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$。 输入中的所有数值都是整数。在第一次查询时，只有顶点 $4$ 可通过若干条边在 $G$ 上从顶点 $4$ 到达。 在第三次查询时，顶点 $2$、$3$、$4$ 和 $5$ 可通过若干条边在 $G$ 上从顶点 $4$ 到达。 在第五次查询时，顶点 $1$、$2$、$3$、$4$ 和 $5$ 可通过若干条边在 $G$ 上从顶点 $4$ 到达。

标签: AtCoder|abc295G

来源

AtCoder|abc295G