Jingle Balls#7022
Tezliklə Milad ağacını bəzəmək vaxtı gələcək. NWERC hakimləri artıq ağacı bəzəməyin ən yaxşı yolunu müzakirə edirlər. Onlar razılaşırlar ki, bəzəklərin ağacın budaqları üzərində bərabər paylanması vacibdir.
Bu problem yalnız ikili Milad ağacları ilə məhdudlaşır. Belə ağaclar gövdədən başlayır və iki alt ağaca bölünür. Hər bir alt ağac öz növbəsində iki kiçik alt ağaca və s. bölünə bilər. Daha da bölünməyən alt ağac budaqdır. Budaq üzərinə ən çox bir top bağlanaraq bəzədilə bilər.
Şəkil 1 – Alt ağaclar, budaqlar və bir top ilə ağac nümunəsi.
Bəzədilmiş ağacın topların bərabər paylanması yalnız və yalnız aşağıdakı şərtin yerinə yetirilməsi ilə mümkündür:
Bir (alt) ağac iki kiçik alt ağaca t_1 və t_2 bölündüyü hər nöqtədə, sol alt ağacdakı topların ümumi sayı N(t_1) və sağ alt ağacdakı topların ümumi sayı N(t_2) ya bərabər olmalıdır, ya da bir fərqlənməlidir. Yəni: |N(t1)-N(t2)| ≤ 1.
Həvəslə, hakimlər əvvəlcə ağacın təsadüfi budaqlarına toplar bağlayırlar. Ağaca daha çox top yerləşdirə bilmədikdə, geri çəkilib nəticəni nəzərdən keçirirlər. Əksər hallarda, topların paylanması tam bərabər olmur. Onlar bunu topları fərqli budaqlara köçürməklə düzəltməyə qərar verirlər.
Ağacın quruluşu və topların ilkin yerləri verildikdə, yuxarıda müəyyən edilmiş bərabər paylanmaya nail olmaq üçün minimum neçə topun köçürülməli olduğunu hesablayın.
Qeyd edək ki, ağaca yeni toplar əlavə etmək və ya topları daimi olaraq çıxarmaq icazəli deyil. Ağacın dəyişdirilməsinin yeganə yolu topları fərqli budaqlara köçürməkdir.
Hər bir test üçün giriş bir bəzədilmiş ağacı təsvir edən bir sətirdən ibarətdir.
Ağacın təsviri onun alt ağaclarının rekursiv təsvirindən ibarətdir. Bir (alt) ağac aşağıdakı formalardan birində olan bir sətirlə təmsil olunur:
'()' sətiri topu olmayan bir budağı təmsil edir.
'(B)' sətiri üzərinə top bağlanmış bir budağı təmsil edir.
'(t_1 t_2)' sətiri iki kiçik alt ağaca bölünən bir (alt) ağacı təmsil edir, burada t_1 və t_2 burada sadalanan formalardan birində olan sətirlərdir.
Bir ağac ən azı 2 və ən çox 1000 budaqdan ibarətdir.
Hər bir test üçün bir sətir çıxış verin.
Əgər topları ağac boyunca bərabər paylamaq mümkündürsə, bərabər paylanma tələbinə cavab vermək üçün köçürülməli olan minimum top sayını çap edin.
Əgər topları bərabər paylamaq mümkün deyilsə, 'impossible' sözünü çap edin.
Nümunə 1