苹果树

Problem Description

给出一棵包含 $n$ 个点的树，每个节点 $i$ 都有一个权值 $a_i$。 有 $m$ 次操作，每次操作都形如以下的两种：

• 1 x y：查询 $x$ 到 $y$ 的路径上，最大的点权权值。
• 2 x z：对于所有与 $x$ 直接相连的点 $i$，令 $a_i \gets a_i + z$。 不保证查询的 $x, y$ 满足 $x \neq y$。

Input

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T(1 \leq T \leq 110)$，表示数据组数。对于每组测试数据： 第一行两个正整数 $n, m(1 \leq n, m \leq 10^5)$。 第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n(1 \leq a_i \leq 10^4)$，表示初始每个节点的点权。 接下来 $n - 1$ 行，每行两个正整数 $x, y(1 \leq x, y \leq n)$，表示有一条从 $x$ 到 $y$ 的无向边。 接下来 $m$ 行，每行三个整数，第一个数 $\mathrm{opt}$ 表示操作类型：

• 若 $\mathrm{opt} = 1$，则后面两个数 $x, y(1 \leq x, y \leq n)$，表示询问路径。
• 若 $\mathrm{opt} = 2$，则后面两个数 $x, z(1 \leq x \leq n, 1 \leq z \leq 10^4)$，分别表示修改中心以及增加的值。 保证所有测试数据中 $n$ 之和与 $m$ 之和均不超过 $4 \times 10^5$。

Output

对于每组测试数据：对于每一个 $\mathrm{opt} = 1$ 的操作，输出一行一个数表示答案。

Sample Input

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

Sample Output

9
11
17
13

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（2）