Дамжуулах Хурдны Нийлбэр

2s

512MB

2100

0%

Advanced Graph Problems

Компьютерын сүлжээнд $n$ компьютер, хоёр компьютерийн хооронд $n-1$ холболт байна. Холболтуудыг ашиглан компьютерийн хос бүр мэдээлэл солилцож чадна.

Холболт бүр тодорхой дамжуулах хурдтай. $d(a,b)$ нь $a$ болон $b$ компьютеруудын хоорондох дамжуулах хурд бөгөөд $a$ -ас $b$ руу зам дээрх хамгийн удаан холболтын хурд юм. Компьютеруудын бүх хосуудын хоорондох дамжуулах хурдны нийлбэрийг тооцоол.

https://cses.fi/problemset/task/3111

Оролтын формат

Эхний мөрөнд $n$ бүхэл тоо: компьютерийн тоо. Компьютерууд $1,2,\dots,n$ гэж дугаарлагдсан.

Дараагийн $n-1$ мөрөнд холболтууд. Мөр бүр $a$ , $b$ , $x$ гэсэн гурван бүхэл тоог агуулна: $a$ болон $b$ компьютеруудын хооронд $x$ дамжуулах хурдтай холболт бий.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: дамжуулах хурдны нийлбэр.

Хязгаарлалт

$1 \le n \le 2 \cdot 10^5$
$1 \le x \le 10^6$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...