CF1491H Yuezheng Ling and Dynamic Tree

乐正绫送给洛天依一棵有 $n$ 个节点的树，根节点为 $1$。 洛天依会告诉你第 $i$ 个节点的父节点是 $a_i$（对于 $2 \leq i \leq n$，有 $1 \leq a_i < i$），并且她会让你进行 $q$ 次两种类型的操作： 1. 她会给你三个整数 $l$、$r$ 和 $x$（$2 \leq l \leq r \leq n$，$1 \leq x \leq 10^5$）。你需要将所有满足 $l \leq i \leq r$ 的 $a_i$ 替换为 $\max(a_i-x,1)$。 2. 她会给你两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$）。你需要求出节点 $u$ 和 $v$ 的最近公共祖先（LCA）。

第一行包含两个整数 $n$ 和 $q$（$2 \leq n, q \leq 10^5$），分别表示节点数和操作数。 第二行包含 $n-1$ 个整数 $a_2, a_3, \dots, a_n$（$1 \leq a_i < i$），其中 $a_i$ 表示节点 $i$ 的父节点。 接下来的 $q$ 行，每行表示一个操作。每行的第一个整数是 $t$（$t=1$ 或 $2$），表示操作类型。 - 如果 $t=1$，表示第一种操作。接下来有三个整数 $l$、$r$、$x$（$2 \leq l \leq r \leq n$，$1 \leq x \leq 10^5$），表示将所有 $l \leq i \leq r$ 的 $a_i$ 替换为 $\max(a_i-x,1)$。 - 如果 $t=2$，表示第二种操作。接下来有两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），你需要求出 $u$ 和 $v$ 的最近公共祖先。 保证至少有一次第二种操作。

对于每个第二种操作，输出一行答案。

样例中的树结构如下图所示。  经过一次第一种操作后，树结构变为如下图所示。  由 ChatGPT 4.1 翻译