Çimbulak
Çimbulak
Məşhur Qazax kurortu Çimbulakda turistlər üçün aralarında eyni uzunluqda yollar salınmış n sayda cəzbedici istirahət yerləri var. Yollar elə salınıb ki, hər bir yol ilə istənilən istiqamətdə hərəkət etmək mümkündür, lakin bəzən bunun üçün çox sayda yerdəyişmə etmək lazım gəlir. Yeni yollar salmazdan əvvəl, kurortun İnzibaçıları bir-birindən daha uzaqda yerləşən bütün dincəlmək üçün yerlər cütlüyü arasında nə qədər müxtəlif yolların olmasını bilmək istəyirlər.
"Bir-birindən daha uzaqda yerləşən yerlər" kimi aralarındakı ən qısa məsafənin maksimum olduğu cütlüklər başa düşülür. Cavab kimi bütün bu cür yerlər cütlükləri arasındakı ən qısa yolların sayının cəmini tapmaq tələb olunur.
Giriş verilənləri
İlk sətirdə n (3 ≤ n ≤ 200 000) ədədi verilir. Növbəti n sətrin hər birində 2 ədəd verilir – aralarında uyğun yolun salındığı istirahət yerlərinin nömrəsi. Bütün yolların müxtəlif istirahət yerləri cütlüklərini birləşdirdiyinə zəmanət verilir.
Çıxış verilənləri
Yeganə ədədi – bir-birindən daha uzaqda yerləşən bütün istirahət yerləri cütlükləri arasındakı ən qısa yolların sayını verməli.
6 1 2 1 3 2 4 4 3 4 5 4 6
4
4 1 2 1 3 1 4 4 3
2
Şərh: Birinci nümunədə bir-birindən daha uzaq məsafədə yerləşən yerlər bunlardır – 1, 5 və 1, 6. Bütün bu yerlər cütlüyü arasında iki müxtəlif yollar var, buna görə də bu nümunədə cavab 4-dür.