Використовуйте дерево відрізків
Задано дерево з 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 рядків задають список запитів, кожен з яких складається з чотирьох цілих чисел у наведеному нижче форматі. Запити потрібно опрацьовувати послідовно зверху вниз.
Вихідні дані
Для кожного запиту вивести у окремому рядку найбільшу суму.