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$ 类操作的答案。

输入输出样例 #1

输入 #1

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

输出 #1

4
2
1

输入输出样例 #2

输入 #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

说明/提示

限制条件

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