H. Piroqolandiya
Piroqolandiya, piroqları çox sevən insanların yaşadığı bir ölkədir. Burada n çörəkxana var və hər biri 1-dən n-ə qədər unikal nömrəyə malikdir. Hər çörəkxananın öz anbarı var və i nömrəli çörəkxanada a[i] piroq saxlanılır.
Çörəkxanalar arasında piroqların daşınması üçün n - 1 yol çəkilib. i-ci yol u[i] və v[i] çörəkxanalarını birləşdirir, yəni bu iki çörəkxana arasında piroq daşınması mümkündür.
u və v çörəkxanaları arasındakı yolu p[1], p[2], ..., p[k] ardıcıllığı ilə təsvir edirik ki, burada hər bir i üçün p[i] və p[i+1] arasında yol var və p[1] = u və p[k] = v. Hər çörəkxana cütü arasında yalnız bir yol var və heç bir çörəkxana iki dəfə ziyarət edilmir.
Zəlzələlər səbəbindən bəzi yollar bağlana bilər və piroqlar bu yollardan daşına bilməz. Bəzən yollar təmir edilir və yenidən açılır. Hər yol ya açıq, ya da bağlı vəziyyətdədir.
u çörəkxanasının komponenti, u nömrəli çörəkxanadan bağlı yollardan keçmədən gedilə bilən bütün çörəkxanaların çoxluğudur. u çörəkxanası da öz komponentinə daxildir.
Piroqolandiya sakinləri arasında ən məşhuru, illik piroqsevərlər festivalında ən çox piroq yeyən Kozak Vusdur.
Piroqolandiya ilə bağlı m hadisə baş verir və bunlar müxtəlif sorğu tipləri şəklində təqdim edilir. Bəzi sorğulara cavab verməlisiniz.
Cəmi 7 sorğu tipi var:
p nömrəli yolun vəziyyətini dəyişdirin. Əgər yol bağlıdırsa, açın və əksinə.
p nömrəli çörəkxananın komponentinə aid hər çörəkxanaya w piroq əlavə edin.
p nömrəli çörəkxananın komponentinə aid bütün çörəkxanalar piroqlarını p çörəkxanasına daşıyır.
Kozak Vus p nömrəli çörəkxananın anbarındakı piroqların sayını öyrənmək istəyir.
Kozak Vus p nömrəli çörəkxananın komponentindəki piroqların ümumi sayını öyrənmək istəyir.
Kozak Vus p nömrəli çörəkxananın komponentindəki bütün piroqları yeyir.
Kozak Vus, bütün piroqları yemək üçün minimum neçə yolun təmir edilməli olduğunu öyrənmək istəyir.
Qeyd edək ki, 4, 5 və 7 tipli sorğular yalnız cavab tapmalıdır, çörəkxanalar və yollara təsir göstərmir.
Əlaqə Protokolu
Sizdən səkkiz funksiyanı həyata keçirmək tələb olunur:
void init(integer n, array of integers u, array of integers v, array of integers b, array of integers a, integer g)
n — çörəkxanaların sayı;
u[i]vəv[i]— i-ci yolun çəkildiyi çörəkxanalar;b[i]— 1-ə bərabərdirsə, i-ci yol bağlıdır, əks halda 0;a[i]— hər çörəkxanadakı piroqların sayı;g — blok nömrəsi;
bu funksiya yalnız bir dəfə çağırılır.
void query_1(integer p)
p — vəziyyəti dəyişdiriləcək yolun nömrəsi.
void query_2(integer p, integer w)
p — çörəkxananın nömrəsi;
w — əlavə ediləcək piroqların sayı.
void query_3(integer p)
p — çörəkxananın nömrəsi.
integer query_4(integer p)
p — çörəkxananın nömrəsi;
sorğunun cavabını qaytarır.
integer query_5(integer p)
p — çörəkxananın nömrəsi;
sorğunun cavabını qaytarır.
void query_6(integer p)
p — çörəkxananın nömrəsi.
integer query_7()
sorğunun cavabını qaytarır.
Giriş Formatı
Birinci sətir üç tam ədəd n, m və g — çörəkxanaların sayı, hadisələrin sayı və blok nömrəsi.Növbəti n − 1 sətirdə hər biri iki tam ədəd u[i] və v[i] — i nömrəli yolun çəkildiyi çörəkxanalar.
Növbəti sətir n − 1 simvoldan ibarətdir, 0 və ya 1. i-ci simvol 1-dirsə, i nömrəli yol bağlıdır, əks halda 0.
Növbəti sətir n tam ədəd a1, a2, ..., an — hər çörəkxanadakı piroqların sayı.
Növbəti m sətirdə müvafiq sorğuların təsviri var. İlk ədəd sorğunun tipini göstərir. Əgər sorğu 2-ci tipdirsə, p və w parametrlərini ehtiva edir. Əgər sorğu 1-ci tipdirsə, p parametrini ehtiva edir. Əgər sorğu 3-dən 6-ya qədərdirsə, p parametrini ehtiva edir. Əgər sorğu 7-ci tipdirsə, əlavə parametr yoxdur.
Çıxış Formatı
4, 5 və 7 tipli hər sorğu üçün cavabı ayrı sətirdə çıxarın.
Qiymətləndirmə
(2 bal) n ⩽ 3 000; m ⩽ 3 000; 1 və 7 tipli sorğular yoxdur; bütün yollar əvvəlcə bağlıdır;
(3 bal) n ⩽ 3 000; m ⩽ 3 000; 1 və 7 tipli sorğular yoxdur; bütün yollar əvvəlcə açıqdır;
(5 bal) n ⩽ 3 000; m ⩽ 3 000; 1 və 7 tipli sorğular yoxdur;
(6 bal) n ⩽ 3 000; m ⩽ 3 000; 7 tipli sorğular yoxdur;
(8 bal) n ⩽ 3 000; m ⩽ 3 000;
(10 bal) 1 və 7 tipli sorğular yoxdur;
(16 bal) 7 tipli sorğular yoxdur; 1 tipli sorğularda yollar yalnız bağlıdan açığa dəyişdirilir;
(15 bal) 1 tipli sorğular yoxdur;
(9 bal) 7 tipli sorğular yoxdur;
(17 bal) hər çörəkxana ən çox iki digər çörəkxana ilə yol vasitəsilə birləşdirilib;
(9 bal) əlavə məhdudiyyətlər yoxdur;
Qeyd
Şəkillərdə çörəkxanalar içərisində iki tam ədəd olan dairə şəklində təsvir edilmişdir — çörəkxananın nömrəsi və bu çörəkxananın anbarındakı piroqların sayı. Açıq yollar çörəkxanalar arasında düz xəttlə, bağlı yollar isə kəsik xəttlə təsvir edilmişdir.
Şəkil 0-da bütün dəyişikliklərdən əvvəl Piroqolandiya təsvir edilmişdir. 1 və 3 nömrəli çörəkxanalar arasındakı 2 nömrəli yol bağlıdır. 1 nömrəli çörəkxananın komponentində, 2 nömrəli çörəkxana üçün olduğu kimi, 1 və 2 nömrəli çörəkxanalar var. 3, 4 və 5 nömrəli çörəkxanaların komponentində 3, 4 və 5 nömrəli çörəkxanalar var, beləliklə, 3 çörəkxanasının komponentindəki çörəkxanalardakı piroqların sayı 6 + 1 + 3 = 10-a bərabərdir.
İkinci sorğudan sonra (Şəkil 1) 3 və 5 nömrəli çörəkxanalar piroqlarını 4 nömrəli çörəkxananın anbarına daşıyır.
Üçüncü sorğudan sonra (Şəkil 2) 3, 4 və 5 nömrəli çörəkxanalara 4 piroq gətirilir, beləliklə, 3 nömrəli çörəkxananın anbarındakı piroqların sayı 4-ə bərabər olur. 2 nömrəli çörəkxana istisna olmaqla, hər bir çörəkxananın anbarında ən azı 1 piroq var. Əgər Kozak Vus yoluna 1 və ya 2 nömrəli çörəkxanadan başlasa, 3 nömrəli çörəkxanaya çatmaq üçün 2 nömrəli yolu təmir etməlidir. Əgər o, yoluna 3, 4 və ya 5 nömrəli çörəkxanadan başlasa, 1 nömrəli çörəkxanaya çatmaq üçün eyni 2 nömrəli yolu təmir etməlidir. Buna görə də, beşinci sorğunun cavabı 1-ə bərabərdir.
Altıncı sorğudan sonra (Şəkil 3) Kozak Vus 3, 4 və 5 nömrəli çörəkxanaların anbarlarından bütün piroqları yeyir.
Yeddinci sorğudan sonra (Şəkil 4) yol təmir xidməti 2 nömrəli yolu təmir edir, beləliklə, indi bu yol açıq olur. İndi 1 nömrəli çörəkxananın komponentində, bütün digər çörəkxanalar üçün olduğu kimi, Piroqolandiya çörəkxanalarının hamısı var. Buna görə də, səkkizinci sorğunun cavabı 0 + 1 + 0 + 0 + 0 = 1-ə bərabərdir.
Doqquzuncu sorğudan sonra (Şəkil 5) hər bir çörəkxananın anbarına 1 piroq gətirilir.
Onuncu sorğudan sonra (Şəkil 6) zəlzələ nəticəsində 3 nömrəli yol dağıldığı üçün bağlı olur. İndi 1 nömrəli çörəkxananın komponentində 4 nömrəli çörəkxana istisna olmaqla bütün çörəkxanalar var və 4 nömrəli çörəkxananın komponentində yalnız o özü var. Buna görə də, sonuncu sorğunun cavabı 2 + 1 + 1 + 1 = 5-ə bərabərdir.