Koba və banan ağacı
Dostunuz Koba ağıllı meymundur və o banan yeməyi çox sevir.
O, bu gün səhər cəngəllikdə tapdığı banan ağacını kökündən çıxarıb (Koba çox güclüdür) yuvasına apardı. Koba bu gün üç dəfə qəlyanaltı edəcək. Buna görə də o, ağacın iki budağını kəsərək onu üç hissəyə ayırmağı düşünür (hər bir qəlyanaltı üçün hissələrdən birindəki bananları yeyəcək). Koba elə etmək istəyir ki, ən çox banan olan hissə ilə ən az banan olan hissə arasındakı bananların say fərqi mümkün qədər az olsun (Koba balanslı qidalanmağa çalışır). Belə kəsməni optimal kəsmə adlandıracağıq.
Kobanın yuvasına apardığı banan ağacı 1-dən n-ə tam ədədlərlə nömrələnmiş n sayda banandan və bu bananlar arasında birləşdirici rolu oynayan n − 1 sayda budaqdan ibarət əlaqəli qrafdır. Yəni ki, bananlara qrafın təpə nöqtələri, budaqlara isə bu təpə nöqtələri arasında əlaqələr kimi baxa bilərik.
Sizə Kobanın yuvasına apardığı ağacın strukturu verilib. Buna əsasən optimal kəsmədə ən çox banan olan hissə ilə ən az banan olan hissə arasındakı bananların say fərqini tapın.
Giriş verilənləri
Birinci sətirdə bir tam ədəd, n (3 ≤ n ≤ 2 * 10^5) - bananların sayı, növbəti n - 1 sətrin hər birində isə iki tam ədəd, u[i], v[i] (1 ≤ u[i], v[i] ≤ n) - aralarında birbaşa budaq olan banan cütləri verilir.
Çıxış verilənləri
Çıxışa bir tam ədəd, optimal kəsmədə ən çox banan olan hissə ilə ən az banan olan hissə arasındakı bananların say fərqini verin.
İzahat
Nümunə 1. Bu nümunədə 2 ilə 3 və 4 ilə 5 arasındakı budaqları kəssək ağac 2, 2 və 1 ölçülü üç hissəyə ayrılar. Cavab 2 − 1 = 1 olur.
Nümunə 2. Optimal kəsmələr yuxarıda təsvir olunan şəkildə verilmişdir. Kəsmələr nəticəsində yaranan hissələrin ölçüləri 4, 2 və 3-dür. Cavab 4 − 2 = 2 olur.