E. Наибольшее удаление

Дано взвешенное дерево. Для каждой вершины найдите наибольшее взвешенное расстояние от неё до какой-нибудь другой вершины. Для дерева из одной вершины ответ ноль.

Схема та же, что в предыдущей задаче, но с важным отличием: максимум не обратим.

В сумме расстояний вклад «всего остального» удавалось выразить одним числом и пересчитать арифметикой. С максимумом так нельзя: чтобы узнать максимум по всем детям, кроме одного, вычесть ничего не получится.

Два максимума

Стандартное лекарство - хранить в каждой вершине два наибольших значения среди детей и знать, на каком ребёнке достигнут первый.

Тогда «максимум по всем детям, кроме $c$» - это первый максимум, если он достигнут не на $c$, и второй иначе.

down[v] = 0;
for (auto [c, w] : children[v]) down[v] = std::max(down[v], down[c] + w);

Обход вверх: пусть $up[v]$ - наибольшее расстояние от $v$ в часть дерева вне её поддерева. Тогда для ребёнка $c$ с весом ребра $w$:

Ответ для вершины - $\max(down[v], up[v])$.

Проверьте себя

Максимум под $up[c]$ должен браться и с нулём тоже: если у $v$ нет других детей и $v$ - корень, то путь может кончиться в самой $v$, и «лучший спуск среди остальных детей» равен нулю, а не минус бесконечности.

На цепочке из трёх вершин с весами рёбер 5 и 7 ответы должны получиться 12, 7, 12. Если у вас вышло что-то другое - ошибка ровно в этом месте.

Подробнее: «Смена корня».

В первой строке - число $n$ ($1 \le n \le 10^5$).

В следующих $n - 1$ строках - тройки $v$, $u$, $w$ ($1 \le v, u \le n$, $0 \le w \le 10^6$).

Выведите $n$ чисел - наибольшее удаление для каждой вершины.