caravane
В
Сахара има N оазиса,
съединени с
пътища, така
че от всеки
оазис може да
се отиде до
всеки друг и това
става по
единствен начин
(по единствен
път или
по единствена
последователност
от пътища). За
някои двойки
оазиси през
годината се
организират
по два
кервана,
съответно в
едната и в
другата
посока.
Условието да
има организиран
керван между
два оазиса е
пътуването
да може да се осъществи
чрез
преминаване
по точно K пътя.
Така, ако пътуването
между
два оазиса се
извършва по
пътища, чийто
брой е
различен от K, за тази
двойка оазиси
не се
организират
кервани. Главният
халиф решил
да въведе
такси, които
всеки керван
да плаща при ползване
на всеки от
пътищата. Халифът
искал да знае
общата сума
от таксите,
събрани през
годината.
Вход
Входният
файл caravane.in съдържа
в първия си
ред броя на
градовете N и стойността K. Следващите
N-1 реда
съдържат по три
числа,
разделени с
интервали: x, y и t, които
показват, че
съществува
път между оазисите
x и
y, и таксата
за
минаването
по този път е t.
Изход
Изходният
файл caravane.out трябва
да съдържа
един ред с
търсената обща
сума на таксите.
Ограничения
1 < N < 100 000
0 < K < 32
Таксата за
всеки път е положително
цяло число <= 100
Стойността
на общата сума
на събраните
такси
изисква за
записването
си 8-байтово
цяло число
със знак.
Пример
|
caravane.in |
caravane.out |
Обяснение |
|
5 2 |
108 |
Кервани
са
организирани
само между
двойките
оазиси: 1-3, 1-4, 2-5, 3-1, 3-4, 4-1, 4-3 и 5-2,
съответно с
такси 9, 15, 14, 9, 16, 15, 16, и 14. Общата
сума на тези
такси е 108. |
Време
за работа на
програмата: 0.6 секунди за
тест.
Обща разрешена
памет: 30 MB, от която 1 MB за
стек.
student
Gheroghe Stefan
A.S.E. Bucharest
stefangh@gmail.com
Превод на
български:
Емил
Келеведжиев