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!

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.