e-olymp
Yarışlar

ADA Classes - Depth First Search

Cəm

Romanın valideynləri ona n sayda təpəsi və n-1 sayda tilləri olan istiqamətlənməmiş əlaqəli çəkili qraf hədiyyə edirlər. Roman qrafda olan bütün yolların ümumi uzunluğunu tapmaq istəyir. Yolun uzunluğu onda olan tillərin uzunluqlarının cəmidir. Roman hesab edir ki, u-dan v-yə olan yol v-dən u-ya olan yol kimidir, buna görə də o onları fərqləndirmir.

Giriş verilənləri

İlk sətir qrafda olan təpələrin n (2n105) sayını ehtiva edir. Növbəti n-1 sətir qrafın tillərini təsvir edir. Hər sətir üç tam ədəd ehtiva edir: Tilin birləşdirdiyi təpələrin nömrələri (təpələr 1-dən n-ə qədər nömrələnib) və tilin çəkisi.

Çıxış verilənləri

Bütün yolların uzunluqlarının cəmini 109 moduluna görə hesablayın.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
1 2 1
1 3 3
Çıxış verilənləri #1
8

Şərh: Məsələnin izahı. Qrafda olan bütün yollar: 1 → 2, 1 → 3, 2 → 1 → 3, onların uzunluqlarının cəmi 1 + 3 + 4 = 8.

Mənbə 2011 International Collegiate Programming Contest, Ukraine, Quarter-Final, May 19