eolymp
bolt
Try our new interface for solving problems
Məsələlər

Управляющая сеть

Управляющая сеть

Zaman məhdudiyyəti 0.5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Рыбка решила определить критичность управляющей сети Ватсона, в которой есть N узлов, соединенных между собой проводниками. Из каждого узла может быть передан сигнал в любой другой узел по единственно возможному пути. Когда на один из узлов подаётся внешнее воздействие, он передает сигнал каждому другому узлу. То есть после внешнего воздействия узел создает (N–1) сигнал. i-узловая интенсивность (iNode) проводника определяется как произведение его длины на количество сигналов, проходящих через него после внешнего воздействия на узел i. Проводник считается i-критическим, если среди всех проводников его iNode будет максимальным (при фиксированном i). В случае равенства iNode, i-критическими считаются несколько проводников. Суммарная критичность проводника определяется как количество его i-критичностей. Критичность всей сети определяется как максимум из суммарных критичностей его проводников.

Giriş verilənləri

В первой строке задано одно целое число N – число узлов, далее (N-1) строка, в каждой из которых указаны три целых числа i, j, A – параметры проводника, который соединяет узлы i и j и имеет длину A.

2N10^5, (1i, jN, 1A10^5).

Çıxış verilənləri

Вывести значение критичности сети

Пояснение: В сети 1-критичный проводник 1, 2-критичные: 1, 2, 3-критичные: 1, 4-критичные: 3, 5-критичные: 4. Значит, 1-й проводник имеет три критичности, поэтому его суммарная критичность равна 3, суммарная критичность других проводников равна по 1, критичность всей сети равна максимуму из суммарных критичностей проводников, то есть 3.

Nümunə

Giriş verilənləri #1
5
1 2 3
2 3 1
3 4 1
3 5 1
Çıxış verilənləri #1
3