Segment ağacından istifadə edin
Verilmiş ağac n (1 ≤ n ≤ 200000) zirvələri və q (1 ≤ q ≤ 100000) sorğular siyahısı ilə müəyyən edilir. Bütün sorğuları işləyib hər biri üçün cavab çıxarmaq tələb olunur. Ağac əlaqəlidir və hər bir zirvəyə w_i (−10000 ≤ w_i ≤ 10000) çəkisi təyin olunub.
Hər bir sorğu t_i (t_i = 1, 2) - sorğu tipindən və üç ədəd a_i, b_i və c_i (1 ≤ a_i, b_i ≤ n, −10000 ≤ c_i ≤ 10000) ibarətdir. Sorğunun tipinə görə aşağıdakıları yerinə yetirmək lazımdır:
(t_i = 1: modifikasiya sorğusu) a_i və b_i zirvələri arasında (hər iki daxil olmaqla) ən qısa yolda olan bütün zirvələrin çəkilərini c_i ilə dəyişdirin.
(t_i = 2: çıxış sorğusu) Əvvəlcə a_i və b_i arasında (hər iki daxil olmaqla) ən qısa yolda olan zirvələrin çəkilərinin siyahısını keçid ardıcıllığı ilə yaradın. Sonra siyahıda ardıcıl olan ən böyük cəmi olan boş olmayan alt ardıcıllığın çəkilərini çıxarın. Bu sorğu tipində c_i dəyəri nəzərə alınmır.
Giriş verilənləri
Birinci sətir iki tam ədəd n və q ehtiva edir. İkinci sətirdə n tam ədəd w_1, w_2, ..., w_n verilib. Növbəti n−1 sətirin hər biri s_i və e_i (1 ≤ s_i, e_i ≤ n) iki ədədini ehtiva edir ki, bu da s_i və e_i arasında bir kənarın mövcud olduğunu göstərir.
Növbəti q sətir sorğular siyahısını təyin edir, hər biri aşağıda göstərilən formatda dörd tam ədəddən ibarətdir. Sorğular yuxarıdan aşağıya doğru ardıcıl işlənməlidir.
Çıxış verilənləri
Hər bir sorğu üçün ayrı sətirdə ən böyük cəmi çıxarın.