题号：NC14649
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
kotomi 有一棵树。树上有n个房子，编号1-n，每个房子有一个快乐值。
kotomi想知道从a房子到b房子路径上的最大快乐值或者路径山疙瘩快乐值的和。
并且kotomi可以改变任意一个房子的快乐值。
具体如下
(1) 0 a b:查询a到b路径上的最大快乐值(包含a和b)
(2) 1 a b:查询a到b路径上的所有房子快乐值的和。（包含a和b）
(3) 2 x y：将编号为x的房子的快乐值改为y。
输入描述:
多组测试数据第一行有两个整数n，q。表示有n个房子，q次操作。第二行有n个整数v1,v2...vn,表示编号为i的房子的快乐值vi接下来n-1行，每行两个整数u,v，表示编号为u和编号为v的房子之间有一条直接路径。接下来p行，每行开头一个整数（0，1或2）表述操作类型，每个操作后有两个整数。
输出描述:
对于操作为0和1的输出对应的值。