CF1575I Illusions of the Desert

Chanek Jones 回来了，他正在帮助他失散多年的亲戚 Indiana Jones，在一片充满幻象的沙漠下方的迷宫中寻找一份秘密宝藏。 迷宫的地图构成了一棵有 $n$ 个房间的树，这些房间编号为 $1$ 到 $n$，并且有 $n-1$ 条隧道连接它们，使得每一对房间之间都可以通过若干条隧道互相到达。 第 $i$ 个房间（$1 \leq i \leq n$）有一个幻象率 $a_i$。要从第 $x$ 个房间走到第 $y$ 个房间，必须存在一条连接 $x$ 和 $y$ 的隧道，所需能量为 $\max(|a_x + a_y|, |a_x - a_y|)$。其中 $|z|$ 表示 $z$ 的绝对值。 为了防止盗墓者，迷宫可以随时改变任意房间的幻象率。Chanek 和 Indiana 会向你提出 $q$ 个询问。 询问有两种类型： - $1\ u\ c$ — 将第 $u$ 个房间的幻象率改为 $c$（$1 \leq u \leq n$，$0 \leq |c| \leq 10^9$）。 - $2\ u\ v$ — 他们询问：如果他们初始在第 $u$ 个房间，前往第 $v$ 个房间拿到秘密宝藏，所需的最小能量和是多少（$1 \leq u, v \leq n$）。 请帮助他们，这样你也能分到一份宝藏！

第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 10^5$，$1 \leq q \leq 10^5$）——迷宫中的房间数和询问数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq |a_i| \leq 10^9$）——每个房间的初始幻象率。 接下来 $n-1$ 行，每行包含两个整数 $s_i$ 和 $t_i$（$1 \leq s_i, t_i \leq n$），表示存在一条连接第 $s_i$ 个房间和第 $t_i$ 个房间的隧道。给定的边构成一棵树。 接下来的 $q$ 行，每行是一个如上所述的询问。所有询问均合法。

对于每个类型为 $2$ 的询问，输出一行一个整数，表示 Chanek 和 Indiana 拿到秘密宝藏所需的最小能量和。

 在第一个询问中，他们从第 $1$ 个房间移动到第 $2$ 个房间的过程如下： - $1 \rightarrow 5$ —— 需要的能量为 $\max(|10 + 4|, |10 - 4|) = 14$。 - $5 \rightarrow 6$ —— 需要的能量为 $\max(|4 + (-6)|, |4 - (-6)|) = 10$。 - $6 \rightarrow 2$ —— 需要的能量为 $\max(|-6 + (-9)|, |-6 - (-9)|) = 15$。 总共需要 $39$ 能量。 在第二个询问中，第 $1$ 个房间的幻象率从 $10$ 变为 $-3$。 在第三个询问中，他们从第 $1$ 个房间移动到第 $2$ 个房间的过程如下： - $1 \rightarrow 5$ —— 需要的能量为 $\max(|-3 + 4|, |-3 - 4|) = 7$。 - $5 \rightarrow 6$ —— 需要的能量为 $\max(|4 + (-6)|, |4 - (-6)|) = 10$。 - $6 \rightarrow 2$ —— 需要的能量为 $\max(|-6 + (-9)|, |-6 - (-9)|) = 15$。 现在总共需要 $32$ 能量。 由 ChatGPT 4.1 翻译