Illusions of the Desert

题意翻译

给定一棵 $n$ 个节点的树，树有点权。若有一条边 $(u,v)$，记节点 $x$ 的点权为 $a_x$，则通过这条边需要 $\max(|a_u+a_v|,|a_u-a_v|)$ 的时间。 共有 $q$ 个询问或操作，格式为： - `1 u c`：将第 $u$ 个节点的点权改为 $c$； - `2 u v`：询问从 $u$ 走到 $v$ 需要的时间。

题目描述

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.

输入输出样例

输入样例 #1

6 4
10 -9 2 -1 4 -6
1 5
5 4
5 6
6 2
6 3
2 1 2
1 1 -3
2 1 2
2 3 3

输出样例 #1

39
32
0

说明

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.