Çox Sonlu Hekayə#3288

Çox Sonlu Hekayə

5 saniyə
64 meqabayt
Çox asan

Bir proqramçı olaraq bishojo oyunlarına (tanışlıq simulyasiya oyunlarının bir alt janrı) olan sevginizi bilirik. "I * C * P * C!" adlı oyun dünən buraxıldı və artıq sizə çatdı. Bu oyunun bir neçə sonu var. Bütün bu sonları tamamladığınızda, əsas qəhrəman Sakuya'nın xüsusi bir fiqurunu əldə edə bilərsiniz. Buna görə də, oyunu oynamaq üçün tələsirsiniz! Amma gəlin bir az sakitləşək və əvvəlcə bütün sonları ən qısa zamanda necə tamamlayacağımızı düşünək.

Əslində, oyunların budaqlanma nöqtələrinin strukturunu bilmək üçün xüsusi bir bacarığınız var. Bu bacarıqdan istifadə edərək, bu oyundakı bütün budaqlanma nöqtələrinin "Bəli" və ya "Xeyr" seçimlərini etmək olduğunu və fərqli bir seçim edildikdə budaqlanan hekayələrin fərqli sonlara axdığını, daha birləşmədiyini, ikili ağac kimi olduğunu öyrəndiniz. Həmçinin, bir budaqlanma nöqtəsindən digərinə və ya sona keçmək üçün dəqiq bir dəqiqə vaxt tələb etdiyini gördünüz. Bundan əlavə, oyunun başlanğıcına qayıtmaq ("sıfırlamaq") və başlanğıcdan ilk budaqlanma nöqtəsinə qədər oynamaq üçün əhəmiyyətsiz vaxt tələb etdiyini fərz edə bilərsiniz.

Oyunun "Sürətli Yadda Saxla" adlı əlavə bir xüsusiyyəti var ki, bu da tamamlanma üçün oynama vaxtını əhəmiyyətli dərəcədə azalda bilər. Bu xüsusiyyət, hazırda oynadığınız nöqtəni qeyd etməyə və daha sonra istənilən vaxt ora qayıtmağa imkan verir. İstənilən sayda qeyd edə bilərsiniz, lakin yalnız son qeyd olunan nöqtəni saxlaya bilərsiniz. Yəni, Sürətli Yadda Saxla istifadə etdikdə, əvvəlki qeydi üstələyirsiniz. Üstələnmiş nöqtəyə qayıtmaq istəyirsinizsə, oyunu yenidən başlanğıcdan oynamalısınız.

Yaxşı, gəlin bütün sonları ən qısa zamanda tamamlamanın nə qədər vaxt alacağını təxmin edək.

Giriş

Məlumat dəsti aşağıdakı formatda verilir.

N

2 ≤ N ≤ 500,000

N−1

i

Yes_i

No_i

i+1 ≤ Yes_i, No_i ≤ N

Yes_i=N

No_i=N

N−1

Yes_i

No_i

Məlumat dəstinin ilk sətri bu oyundakı sonların sayını göstərən bir tam ədədi () ehtiva edir. Sonrakı sətirlər budaqlanma nöqtələrini təsvir edir. -ci sətir i nömrəli budaqlanma nöqtəsini təsvir edir və Bəli və ya Xeyr seçdiyiniz zaman növbəti budaqlanma nöqtələrinin ID nömrələrini göstərən iki tam ədəd və () ehtiva edir. Bəli seçsəniz bir sona çata biləcəyinizi bildirir və üçün də eyni. 1 ID nömrəli budaqlanma nöqtəsi ilk budaqlanma nöqtəsidir. 2 ilə (daxil olmaqla) arasında olan ID nömrəli budaqlanma nöqtələri 'lərdə və 'lərdə dəqiq bir dəfə görünür.

Çıxış

Ən qısa vaxtı bir sətirdə yazdırın.

Nümunələr

Nümunə 1

Loading
Loading