Delegasiya (Qızıl)#10125
Fermer Conun ferması otlaqdan ibarətdir və bu otlaqlar n-1 yolla birləşdirilib ki, hər hansı bir otlaqdan digərinə keçmək mümkündür. Başqa sözlə, ferma ağac strukturundadır. 28 il ərzində ağaclarla bağlı mürəkkəb alqoritmik problemlərlə məşğul olduqdan sonra, Con bu strukturu çox mürəkkəb hesab etdi. O düşünür ki, alqoritmik tapşırıqlar yollar üzərində daha sadə həll olunur.
Onun planı yolları bərabər uzunluqlu bir neçə hissəyə bölmək və hər bir hissəni fərqli bir işçiyə həvalə etməkdir. Mübahisələrin qarşısını almaq üçün o, bütün yolların eyni uzunluqda olmasını istəyir. Con maraqlanır ki, hansı uzunluqlara belə bir bölgü mümkündür.
Daha dəqiq desək, hər (1 \leq k \leq n-1) üçün, yolları dəqiq uzunluqda bölmək mümkün olub-olmadığını müəyyənləşdirin.
Birinci sətir bir tam ədəd (2 \leq n \leq 10^5) ehtiva edir.Növbəti n-1 sətirin hər biri iki tam ədəd və ehtiva edir, bu da və zirvələri arasında yolu ifadə edir. və 1, 2, \ldots, n aralığındadır.
Cavab bit sətrini, uzunluğu n-1 olan ədədlərdən ibarət şəkildə çıxarın. Hər (1 \leq k \leq n-1) üçün, sətrin soldan -cı biti -ə bərabər olmalıdır, əgər ağacın yollarını dəqiq uzunluqda hissələrə bölmək mümkündürsə, əks halda .
Nümunədə verilmiş ağacı k = 1, 2, 3 uzunluqlu hissələrə bölmək mümkündür. k = 3 üçün mümkün yol dəsti belədir:
13–12–11–8, 10–9–8–6, 7–6–2–3, 5–4–2–1Nümunə 1