Mərkəzi şəhərdə banditlər#9439
Daha uzun müddət mərkəzi şəhərdə su problemi yox idi. Şəhərin kanalizasiya sistemi köklü bir ağac kimidir: mərkəzi rezervuar kökdə, evlər isə yarpaqlardadır. Su mərkəzi rezervuardan evlərə ağacın kənarları boyunca gedən borularla axır. Hər evdə suya çıxış var.
Birdən banditlər bəzi evləri ələ keçirdilər. Şəhərin meri olaraq siz çox narahatsınız və banditləri qovmaq istəyirsiniz. Beləliklə, banditlər tərəfindən ələ keçirilən evlərə su axınını dayandırmaq istəyirsiniz. Bunun üçün bəzi kanalizasiya borularını tıxaya bilərsiniz. Əgər rezervuardan evə gedən yolda heç olmasa bir tıxanmış boru varsa, evdə suya çıxış yoxdur.
Siz banditlərdən çox qorxursunuz, buna görə də bu, qəza kimi görünsün deyə minimum sayda borunu tıxamağa qərar verdiniz. Bununla yanaşı, şəhər sakinlərinə qayğı göstərirsiniz, ona görə də seçilmiş tıxanmış boruların sayında banditlərsiz və suya çıxışı olmayan evlərin sayını minimuma endirmək istəyirsiniz.
Təəssüf ki, banditlər bəzi evlərdən çıxa və ya bəzi evlərə girə bilərlər. Beləliklə, banditlərin hər yer dəyişməsindən sonra minimum tələb olunan tıxanmış boruların sayını və banditlərsiz və suya çıxışı olmayan evlərin minimum sayını alimlərdən soruşursunuz.
Birinci sətir və q~(2 \le n \le 10^5, 1 \le q \le 10^5) — kanalizasiyanı təmsil edən ağacın zirvələrinin sayı və banditlərin yer dəyişmələrinin sayı olan iki tam ədəd ehtiva edir.
İkinci sətir kanalizasiya təsvirini ehtiva edir: n - 1 tam ədəd p_2, p_3, ..., p_n ardıcıllığı, burada p_i zirvə -nin valideynidir (1 \le p_i < i). Mərkəzi rezervuar zirvə -də yerləşir.
Növbəti sətir banditlərin yer dəyişmələrini təsvir edir. Hər dəyişiklik iki fərqli tipdən biri ola bilər:
"" — banditlər zirvə -dəki evi ələ keçirirlər,
"" — banditlər zirvə -dəki evi tərk edirlər.
Əvvəlcə bütün evlər banditlərdən azaddır. Bütün dəyişikliklər düzgün ardıcıllıq təşkil edir: banditlər artıq ələ keçirilmiş evi ələ keçirə bilməzlər və banditlər ələ keçirilməmiş evi tərk edə bilməzlər.
tam ədəd çıxarın, hər sətirdə iki ədəd: c_i — minimum tıxanmış boruların sayı və h_i — seçilmiş c_i üçün banditlərsiz və suya çıxışı olmayan evlərin minimum sayı.
Nümunə 1