← 返回题目列表

Codeforces · 1083/C

C. 最大墨西哥

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

一旦 Grisha 发现一棵树(无循环的连通图),其根位于节点 $$$1$$$ 中。

但这棵树不仅仅是一棵树。从 $$$0$$$ 到 $$$n - 1$$$ 的整数排列 $$$p$$$ 写入节点中,数字 $$$p_i$$$ 写入节点 $$$i$$$ 中。

由于 Grisha 喜欢为自己发明一些奇怪而有趣的问题,但并不总是能解决它们,你需要帮助他处理这棵树上的两种类型的查询。

让我们定义一个函数$$$MEX(S)$$$,其中$$$S$$$是一组非负整数,作为不包含在该集合中的最小非负整数。

让 $$$l$$$ 成为该树中的简单路径。因此,我们将 $$$l$$$ 上的节点索引定义为 $$$u_1$$$、$$$u_2$$$、$$$\ldots$$$、$$$u_k$$$。

将 $$$V(l)$$$ 定义为集合 {$$$p_{u_1}$$$, $$$p_{u_2}$$$, $$$\ldots$$$ , $$$p_{u_k}$$$}。

那么查询是:

1. 对于两个节点 $$$i$$$ 和 $$$j$$$,交换 $$$p_i$$$ 和 $$$p_j$$$。
2. 找出所有可能的$$$l$$$中$$$MEX(V(l))$$$的最大值。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 树的节点数。

第二行包含 $$$n$$$ 整数 — $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$0\leq p_i < n$$$) — 排列 $$$p$$$,保证所有数字都不同。

第三行包含 $$$n - 1$$$ 整数 — $$$d_2$$$、$$$d_3$$$、$$$\ldots$$$、$$$d_n$$$ ($$$1 \leq d_i < i$$$),其中 $$$d_i$$$ 是树中节点 $$$i$$$ 的直接祖先。

第四行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。

以下 $$$q$$$ 行包含查询的描述:

在接下来的 $$$q$$$ 行的开头,有一个整数 $$$t$$$($$$1$$$ 或 $$$2$$$)——查询的类型:

1. 如果 $$$t = 1$$$,则该行还包含两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq n$$$) — 节点的索引,其中应交换排列值。
2. 如果$$$t = 2$$$,则需要​​在所有可能的$$$l$$$中找到$$$MEX(V(l))$$$的最大值。

输出

对于每个类型 2 查询,打印一个整数 - 该查询的答案。

示例

输入 #1

6
2 5 0 3 1 4
1 1 3 3 3
3
2
1 6 3
2

输出 #1

3
2

输入 #2

6
5 2 1 4 3 0
1 1 1 3 3
9
2
1 5 3
2
1 6 1
2
1 4 2
2
1 1 6
2

输出 #2

3
2
4
4
2

注意

括号内的数字是节点的排列值。