CF1575I.Illusions of the Desert

Chanek Jones is back, helping his long-lost relative Indiana Jones, to find a secret treasure in a maze buried below a desert full of illusions.

The map of the labyrinth forms a tree with $n$ rooms numbered from $1$ to $n$ and $n - 1$ tunnels connecting them such that it is possible to travel between each pair of rooms through several tunnels.

The $i$-th room ($1 \leq i \leq n$) has $a_i$ illusion rate. To go from the $x$-th room to the $y$-th room, there must exist a tunnel between $x$ and $y$, and it takes $\max(|a_x + a_y|, |a_x - a_y|)$ energy. $|z|$ denotes the absolute value of $z$.

To prevent grave robbers, the maze can change the illusion rate of any room in it. Chanek and Indiana would ask $q$ queries.

There are two types of queries to be done:

• $1\ u\ c$ — The illusion rate of the $x$-th room is changed to $c$ ($1 \leq u \leq n$, $0 \leq |c| \leq 10^9$).
• $2\ u\ v$ — Chanek and Indiana ask you the minimum sum of energy needed to take the secret treasure at room $v$ if they are initially at room $u$ ($1 \leq u, v \leq n$).

Help them, so you can get a portion of the treasure!

查内克·琼斯再度归来，协助他失散多年的亲戚印第安纳·琼斯，在一片充满幻象的沙漠之下寻找一座迷宫中的秘密宝藏。

该迷宫的地图构成一棵树，包含 $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$ 的绝对值。

为防止盗墓者闯入，迷宫可随时更改任意房间的幻象率。查内克与印第安纳将提出 $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$）

请帮助他们，这样你也能分得一份宝藏！

The first line contains two integers $n$ and $q$ ($2 \leq n \leq 10^5$, $1 \leq q \leq 10^5$) — the number of rooms in the maze and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq |a_i| \leq 10^9$) — inital illusion rate of each room.

The $i$-th of the next $n-1$ lines contains two integers $s_i$ and $t_i$ ($1 \leq s_i, t_i \leq n$), meaning there is a tunnel connecting $s_i$-th room and $t_i$-th room. The given edges form a tree.

The next $q$ lines contain the query as described. The given queries are valid.

第一行包含两个整数 $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$ 行中，第 $i$ 行包含两个整数 $s_i$ 和 $t_i$（$1 \leq s_i, t_i \leq n$），表示存在一条连接第 $s_i$ 个房间与第 $t_i$ 个房间的隧道。所给的边构成一棵树。

接下来的 $q$ 行按描述给出查询。所有给定的查询均有效。

For each type $2$ query, output a line containing an integer — the minimum sum of energy needed for Chanek and Indiana to take the secret treasure.

对于每个类型 $2$ 的查询，输出一行，包含一个整数——Chanek 和 Indiana 取得秘密宝藏所需的最小能量总和。

In the first query, their movement from the $1$-st to the $2$-nd room is as follows.

• $1 \rightarrow 5$ — takes $\max(|10 + 4|, |10 - 4|) = 14$ energy.
• $5 \rightarrow 6$ — takes $\max(|4 + (-6)|, |4 - (-6)|) = 10$ energy.
• $6 \rightarrow 2$ — takes $\max(|-6 + (-9)|, |-6 - (-9)|) = 15$ energy.

In total, it takes $39$ energy.

In the second query, the illusion rate of the $1$-st room changes from $10$ to $-3$.

In the third query, their movement from the $1$-st to the $2$-nd room is as follows.

• $1 \rightarrow 5$ — takes $\max(|-3 + 4|, |-3 - 4|) = 7$ energy.
• $5 \rightarrow 6$ — takes $\max(|4 + (-6)|, |4 - (-6)|) = 10$ energy.
• $6 \rightarrow 2$ — takes $\max(|-6 + (-9)|, |-6 - (-9)|) = 15$ energy.

Now, it takes $32$ energy.

在第一次查询中，他们从第 $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$ 单位能量。