Управляющая сеть
Рыбка решила определить критичность управляющей сети Ватсона, в которой есть N узлов, соединенных между собой проводниками. Из каждого узла может быть передан сигнал в любой другой узел по единственно возможному пути. Когда на один из узлов подаётся внешнее воздействие, он передает сигнал каждому другому узлу. То есть после внешнего воздействия узел создает (N–1) сигнал. i-узловая интенсивность (iNode) проводника определяется как произведение его длины на количество сигналов, проходящих через него после внешнего воздействия на узел i. Проводник считается i-критическим, если среди всех проводников его iNode будет максимальным (при фиксированном i). В случае равенства iNode, i-критическими считаются несколько проводников. Суммарная критичность проводника определяется как количество его i-критичностей. Критичность всей сети определяется как максимум из суммарных критичностей его проводников.
Входные данные
В первой строке задано одно целое число N – число узлов, далее (N-1) строка, в каждой из которых указаны три целых числа i, j, A – параметры проводника, который соединяет узлы i и j и имеет длину A.
2 ≤ N ≤ 10^5, (1 ≤ i, j ≤ N, 1 ≤ A ≤ 10^5).
Выходные данные
Вывести значение критичности сети
Пояснение: В сети 1-критичный проводник 1, 2-критичные: 1, 2, 3-критичные: 1, 4-критичные: 3, 5-критичные: 4. Значит, 1-й проводник имеет три критичности, поэтому его суммарная критичность равна 3, суммарная критичность других проводников равна по 1, критичность всей сети равна максимуму из суммарных критичностей проводников, то есть 3.