← 返回题目列表

Codeforces · 1491/H

H. 凌月正与动态树

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

凌月正给了洛天翼一棵树,该树有$$$n$$$个节点,根为$$$1$$$。

洛天依会告诉你第$$$i$$$个节点的父节点是$$$a_i$$$ ($$$1 \leq a_i<i$$$ for $$$2 \le i \le n$$$),她会要求你执行$$$2$$$类型的$$$q$$$查询:

1. 她会给你三个整数 $$$l$$$、$$$r$$$ 和 $$$x$$$ ($$$2 \le l \le r \le n$$$、$$$1 \le x \le 10^5$$$)。您需要将 $$$a_i$$$ 替换为 $$$\max(a_i-x,1)$$$,将所有 $$$i$$$ 替换为 $$$l \leq i \leq r$$$。
2. 她会给你两个整数 $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$)。您需要找到节点 $$$u$$$ 和 $$$v$$$ (它们的最低共同祖先)的 LCA。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2\leq n,q \leq 10^5$$$) — 分别是节点数和查询数。

第二行包含 $$$n-1$$$ 整数 $$$a_2, a_3,\dots, a_n$$$ ($$$1 \le a_i < i$$$),其中 $$$a_i$$$ 是节点 $$$i$$$ 的父节点。

接下来的 $$$q$$$ 行包含查询。对于每个查询,每行的第一个整数是 $$$t$$$ ($$$t = 1$$$ 或 $$$2$$$) — 查询的类型。

如果$$$t = 1$$$,则表示第一种类型的查询。然后,将跟随三个整数: $$$l$$$、$$$r$$$、$$$x$$$ ($$$2 \le l \le r \le n$$$、$$$1 \le x \le 10^5$$$),这意味着您必须将 $$$a_i$$$ 替换为 $$$\max(a_i-x,1)$$$ 并将所有 $$$i$$$ 替换为 $$$l \leq i \leq r$$$。

如果$$$t = 2$$$,则表示第二类查询。然后,后面会出现两个整数:$$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),你必须找到 $$$u$$$ 和 $$$v$$$ 的 LCA。

保证至少有一个第二类型的查询。

输出

对于第二类型的每个查询,在新行上输出答案。

示例

输入 #1

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

输出 #1

3
3
1

注意

示例中的树如下所示。

在第一种类型的查询之后,树发生变化,如下所示。