题号:NC14649
时间限制: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的输出对应的值。
示例1
输入
复制
6 10
2 5 9 10 36 5
1 2
1 3
1 4
2 5
2 6
0 1 4
0 1 6
1 5 6
1 3 6
1 6 3
2 3 10
1 5 3
0 4 5
2 5 100
1 5 4