A14493. 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!

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.

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.

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.