Delegasiya (Qızıl)
Fermer Conun ferması n otlaqdan ibarətdir və bu otlaqlar n - 1 yolla birləşdirilib ki, hər hansı bir otlaqdan digərinə həmişə 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 ağacın çox mürəkkəb olduğunu düşündü. O, hesab edir ki, alqoritmik problemlər yollar üzərində daha sadə həll olunur.
Conun planı yolları bir neçə bərabər uzunluqlu hissəyə bölmək və hər bir hissənin idarəsini layiqli bir ferma sahibinə verməkdir. Mübahisələrin qarşısını almaq üçün o, bütün hissələrin eyni uzunluqda olmasını istəyir. Con maraqlanır ki, hansı uzunluqlar üçün belə bir bölmə mümkündür.
Hər bir k dəyəri üçün (1 ≤ k ≤ n − 1) Cona kömək edin, yolları dəqiq k uzunluğunda bölmək mümkün olub-olmadığını müəyyənləşdirin.
Giriş məlumatları
Birinci sətir bir tam ədəd n (2 ≤ n ≤ 10^5) ehtiva edir. Növbəti n - 1 sətirin hər biri iki tam ədəd a və b ehtiva edir, bu da a və b zirvələri arasında kənarı təsvir edir. Hər bir a və b dəyəri 1 ... n aralığında yerləşir.
Çıxış məlumatları
Uzunluğu n - 1 olan bit sətirini çıxarın. Hər bir k dəyəri üçün (1 ≤ k ≤ n − 1) bu sətirin soldan k-cı biti 1-ə bərabər olmalıdır, əgər ağacın kənarlarını dəqiq k uzunluğunda yollara bölmək mümkündürsə, əks halda 0.
Nümunə
Nümunədə verilmiş ağac k = 1, 2, 3 uzunluğunda yollara bölünə bilər. k = 3 üçün mümkün yol dəsti aşağıdakı kimi görünür:
13−12−11−8,10−9−8−6,7−6−2−3,5−4−2−1