Керуюча мережа#5229

Керуюча мережа

0,5 секунди

64 мегабайти

Дуже складна

Рибка вирішила визначити критичність керуючої мережі Вотсона, яка складається з $N$ вузлів, з'єднаних провідниками. З кожного вузла сигнал може бути переданий до будь-якого іншого вузла лише по унікальному шляху.

При зовнішньому впливі на вузол він передає сигнал кожному іншому вузлу. Тобто, після зовнішнього впливу вузол генерує $(N - 1)$ (N-1) сигналів.

$i$ -інтенсивність ( $i N o d e$ ) для провідника визначається як добуток його довжини на кількість сигналів, що проходять через нього після зовнішнього впливу на вузол $i$ .

Провідник називається $i$ -критичним, якщо його $i N o d e$ -значення є максимальним серед усіх провідників для фіксованого $i$ . У разі рівності $i N o d e$ декілька провідників вважаються $i$ -критичними. Повна критичність провідника визначається як кількість різних $i$ , для яких він є $i$ -критичним. Критичність усієї мережі — це максимальна повна критичність серед усіх провідників.

Вхідні дані

У першому рядку знаходиться одне ціле число $N$ — кількість вузлів. Далі йдуть $(N - 1)$ (N-1) рядків, у кожному з яких три цілих числа $i$ , $j$ , $A$ — опис провідника, що з'єднує вузли $i$ і $j$ довжиною $A$ .

$2 \leq N \leq 1 0^{5}$ 2 \leq N \leq 10^{5}, $1 \leq i, j \leq N$ 1 \leq i, j \leq N, $1 \leq A \leq 1 0^{5}$ 1 \leq A \leq 10^{5}.

Вихідні дані

Виведіть критичність мережі.

Приклади

Приклад 1

Примітка

У даній мережі: $1$ -критичний провідник: $1$ ; $2$ -критичний: $1, 2$ ; $3$ -критичний: $1$ ; $4$ -критичний: $3$ ; $5$ -критичний: $4$ .

Отже, перший провідник має $3$ критичності, тобто його повна критичність — $3$ , повна критичність інших провідників дорівнює $1$ , тому критичність мережі дорівнює $3$ .