Ağacın rənglənməsi#11002
Sizə təpədən ibarət ağac (yönəlməmiş, əlaqəli, tsiksiz qraf) verilmişdir. Siz bu ağac üzərində oyun oynayırsınız.
Əvvəlcə bütün təpələr ağ rəngdədir. Birinci gedişdə siz bir təpə seçib onu qara rəngə boyayırsınız. Sonra hər gedişdə ən azı bir qara təpəyə qonşu (yəni kənarla birləşmiş) olan ağ təpə seçib onu qara rəngə boyayırsınız.
Hər dəfə təpə seçdiyinizdə (ilk gediş də daxil olmaqla), siz seçilmiş təpəni özündə saxlayan, yalnız ağ təpələrdən ibarət əlaqəli komponentin ölçüsünə bərabər xal qazanırsınız. Oyun bütün təpələr qara rəngə boyandıqda başa çatır.
Aşağıdakı nümunəyə baxaq:
və təpələri artıq qara rəngə boyanıb. Əgər təpəsini seçsəniz, və təpələrindən ibarət əlaqəli komponentə görə xal alacaqsınız. Əgər təpəsini seçsəniz, və təpələrindən ibarət əlaqəli komponentə görə xal alacaqsınız.
Sizin tapşırığınız toplaya biləcəyiniz ümumi xal sayını maksimuma çatdırmaqdır.
Birinci sətirdə ağacdakı təpələrin sayını bildirən bir tam ədəd n~(2 \le n \le 2 \cdot 10^5) verilmişdir.
Sonrakı n - 1 sətirdən hər biri ağacın bir kənarını təsvir edir. -ci kənar onun birləşdirdiyi təpələrin nömrələri olan iki tam ədədlə — u_i və v_i~(1 \le u_i, v_i \le n,\ u_i \ne v_i) — verilmişdir.
Verilmiş kənarların ağac əmələ gətirdiyi təminat olunur.
Optimal oyun zamanı əldə edə biləcəyiniz maksimum xal sayını bildirən bir tam ədəd çap edin.
Nümunə 1
Nümunə 2