Qar inəyi Bessi
Na fermaya qar yağdı və Bessi, hər qışın əvvəlində olduğu kimi, qar inəyi düzəltməyə başladı! Əksər vaxt Bessi öz heykəlini həqiqi inəyə mümkün qədər bənzətməyə çalışır. Lakin bu il, bədii ilham hiss edərək, daha abstrakt bir yanaşma seçir və n qar topundan ibarət, n - 1 budaqla birləşdirilmiş ağac şəklində bir heykəl düzəltməyə qərar verir. Hər bir budaq bir cüt qar topunu birləşdirir. Hər bir qar topu cütü arasında unikal bir yol mövcuddur.
Bessi qar toplarından birinə burun əlavə edib, onu abstrakt qar inəyinin başı kimi göstərir. Bu qar topunu 1 nömrəsi ilə işarələyib. Daha çox vizual maraq əlavə etmək üçün, o, bəzi qar toplarını müxtəlif rənglərə boyamağı planlaşdırır, köhnə süd vedrələrini rəngli boyalarla doldurub heykələ səpir. Rənglər 1-dən 10^5-ə qədər tam ədədlərlə təmsil olunur və Bessinin bütün mümkün rənglərdən dolu vedrələrdən məhdudiyyətsiz ehtiyatı var.
Bessi bir qar topuna boya vedrəsi səpdikdə, onun alt ağacındakı bütün qar topları da həmin boya ilə örtülür (qar topu y, qar topu x-in alt ağacında yerləşir, əgər x, y-dən əsas qar topuna gedən yolda yerləşirsə). Hər rəngi diqqətlə səpərək, Bessi qar topuna səpilmiş bütün rənglərin görünməsini təmin edir. Məsələn, əgər qar topu [1, 2, 3] rənglərinə malikdirsə və Bessi onu 4 rəngi ilə örtürsə, qar topu [1, 2, 3, 4] rənglərinə malik olacaq.
Bessi qar toplarını bir neçə dəfə səpdikdən sonra, qar inəyinin bir hissəsinin nə qədər rəngarəng olduğunu bilmək istəyə bilər. Qar topunun x rəngarəngliyi, onun boyandığı müxtəlif rənglərin c sayına bərabərdir. Əgər Bessi sizdən qar topu x haqqında soruşarsa, siz x alt ağacındakı bütün qar toplarının rəngarənglik dəyərlərinin cəmini göstərməlisiniz.
Bessiyə müəyyən vaxtlarda qar inəyinin rəngarəngliyini tapmağa kömək edin.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) və sorğuların sayı q (1 ≤ q ≤ 10^5) ədədini ehtiva edir. Növbəti n - 1 sətirin hər biri, qar toplarını birləşdirən bir budağı təsvir edən iki tam ədəd a və b (1 ≤ a, b ≤ n) ehtiva edir.
Nəhayət, növbəti q sətirin hər biri bir sorğu ehtiva edir. Sorğu növü
1 x c
Bessinin x qar topuna c rəngində boya vedrəsi səpdiyini və x alt ağacındakı bütün qar toplarını boyadığını göstərir.
2 x
sətiri isə x alt ağacındakı bütün qar toplarının rəngarənglik dəyərlərinin cəmi haqqında sorğu deməkdir. Əlbəttə, 1 ≤ x ≤ n və 1 ≤ c ≤ 10^5.
Çıxış məlumatları
Hər 2 tipli sorğu üçün müvafiq alt ağacdakı rəngarənglik dəyərlərinin cəmini göstərin. Qeyd edək ki, daşma qarşısını almaq üçün 64-bit tam ədədlərdən istifadə etməlisiniz.
Nümunə
Birinci 1 tipli sorğudan sonra qar topu 4 rəng 1 ilə boyanır.
İkinci 1 tipli sorğudan sonra qar topları 4 və 5 rəng 1 ilə boyanır.
Üçüncü 1 tipli sorğudan sonra bütün qar topları rəng 1 ilə boyanır.