Mərkəzdə Narfouz#12438
Hamımızın bildiyi kimi, Narfouz Al-Narfouz keyfiyyətsiz məsələləri ilə inəyini əsəbiləşdirməyi sevir. Hətta vəziyyət o yerə çatıb ki, inəyi artıq onun mənzilində elektriki kəsməyə hazırdır!
Narfouzun yaşadığı bina mənzildən və n-1 dəhlizdən ibarət bir ağac şəklində qurulub.
Narfouz aşağıdakı əməliyyatı dəqiq olaraq bir dəfə etmək istəyir:
O, bir mənzili və ona birləşən bütün dəhlizləri siləcək, sonra isə qalan əlaqəli komponentlərdən birinin mərkəzlərindən\Large^{\star} birinə köçəcək.
Əməliyyatı etdikdən sonra, inəyi onun yaşaya biləcəyi bütün mümkün mənzilləri yoxlayacaq və həmin mənzillərin elektriyini kəsəcək!
Narfouz həyəcanla sizdən soruşur: əməliyyatı bir dəfə etdikdən sonra mümkün mənzillərin maksimum sayı nə qədər ola bilər?
\Large^{\star} ağacdakı bir düyün o halda mərkəz sayılır ki, ondan ağacdakı bütün digər düyünlərə olan maksimum məsafə bütün düyünlər arasında minimal olsun.
Birinci sətirdə bir tam ədəd (3 \leq n \leq 2 \times 10^5) verilir — mənzillərin sayı.
Növbəti i+1-ci sətirdə iki ədəd və (1 \leq u,v \leq n) verilir; bunlar -ci dəhlizin uclarını göstərir.
Bir tam ədəd çap edin — əməliyyatı bir dəfə etdikdən sonra Narfouzun yaşaya biləcəyi mümkün mənzillərin maksimum sayı.
Nümunə 1
2_{\mathsf{nd}} mənzil silindikdən sonra üç əlaqəli komponent alınır: , , \{1,6,7,3\}
Birinci əlaqəli komponentdə yeganə mərkəz -dür.
İkinci əlaqəli komponentdə yeganə mərkəz -dir.
Üçüncü əlaqəli komponentdə və düyünləri mərkəz hesab olunur.
Sübut etmək olar ki, əməliyyatı yerinə yetirməyin yeganə optimal yolu budur.
Alt tapşırıq ( xal): -ci dəhliz və i+1 mənzillərini birləşdirir
Alt tapşırıq ( xal): -ci dəhliz və i+1 mənzillərini birləşdirir
Alt tapşırıq ( xal): (1 \leq n \leq 1000)
Alt tapşırıq ( xal): Əlavə məhdudiyyət yoxdur