Используйте дерево отрезков
Задано дерево с n (1 ≤ n ≤ 200000) вершинами и список из q (1 ≤ q ≤ 100000) запросов. Необходимо обработать все запросы и вывести ответ для каждого из них. Дерево является связным, каждой вершине дерева приписан вес w_i (−10000 ≤ w_i ≤ 10000).
Каждый запрос состоит из числа t_i (t_i = 1, 2) - типа запроса, и трех чисел a_i, b_i и c_i (1 ≤ a_i, b_i ≤ n, −10000 ≤ c_i ≤ 10000). В зависимости от типа запроса необходимо совершить следующее:
(t_i = 1: запрос модификации) Изменить веса всех вершин по кратчайшему пути между a_i и b_i (обе включительно) на c_i.
(t_i = 2: запрос вывода) Сначала создайте список весов вершин по кратчайшему пути между a_i и b_i (обе включительно) в порядке обхода. Затем выведите максимальную сумму непустой подряд идущей подпоследовательности весов в списке. Значение c_i игнорируется в этом типе запроса.
Входные данные
Первая строка содержит два целых числа n и q. Во второй строке заданы n целых чисел w_1, w_2, ..., w_n. Каждая из следующих n−1 строк состоит из двух чисел s_i и e_i (1 ≤ s_i, e_i ≤ n), означающих присутствие ребра между s_i и e_i.
Следующие q строк задают список запросов, каждая из которых состоит из четырех целых чисел в приведенном ниже формате. Запросы следует обрабатывать последовательно сверху вниз.
Выходные данные
Для каждого запроса вывести в отдельной строке наибольшую сумму.