Yedek kablo#13117
Bir ülkede n-1 iki yönlü yolla birbirine bağlanmış şehir vardır. Herhangi iki şehir arasında tam olarak bir basit yol bulunur.
Yol ağını daha güvenilir hale getirmek için, doğrudan birbirine bağlı olmayan iki farklı şehir arasına tam olarak bir yeni yol inşa edilecektir.
İnşaattan sonra n-1 bağımsız arıza senaryosu ele alınır. -inci senaryoda yalnızca -inci asıl yol kullanılamaz hale gelir. Yeni yol da dahil olmak üzere diğer tüm yollar kullanılabilir kalır. Her senaryodan önce ağ onarılır.
Bir arızanın yol açtığı hasar, ilgili yol kaldırıldıktan sonra en büyük bağlantılı bileşenin dışında kalan şehirlerin sayısıdır. Tüm şehirler bağlı kalıyorsa hasar sıfırdır.
Yeni yolu, n-1 senaryonun tümündeki hasarların toplamı en küçük olacak şekilde seçin. Bu en küçük toplamı bulun.
İlk satırda bir tam sayı (3\le n\le 2\cdot10^5) — şehirlerin sayısı verilir.
Sonraki n-1 satırın her birinde iki tam sayı u_i,v_i (1\le u_i,v_i\le n, u_i\ne v_i) — -inci asıl yolun uç noktaları verilir.
Asıl yol ağının bir ağaç olduğu garanti edilir.
Bir tam sayı yazdırın — bir yeni yol inşa edildikten sonra elde edilebilecek en küçük hasar toplamı.
Örnek 1
Örnek 2
Örnek 3
Birinci örnekte ve şehirleri arasına bir yol inşa edilebilir. Bundan sonra herhangi bir asıl yoldaki arıza ağın bağlantılılığını bozmaz, bu nedenle cevap 'dır.
İkinci örnekte ve şehirleri arasına bir yol inşa edilebilir. ve yollarındaki arızalar ağın bağlantılılığını bozmaz, yolundaki arıza ise bir şehri yalıtır. Toplam hasar olur.
Üçüncü örnekte yeni yol yalnızca iki asıl yolu koruyabilir. Diğer iki arızanın her biri bir şehri yalıtır, bu nedenle cevap 'dir.
Alt görev ( puan): n\le 9.
Alt görev ( puan): n\le 100.
Alt görev ( puan): n\le 2000.
Alt görev ( puan): en fazla bir şehir asıl yollarla ikiden fazla başka şehre doğrudan bağlıdır.
Alt görev ( puan): ek kısıtlama yoktur.