e-olymp
Соревнования

Dynamic programming on Trees - Top Level

Дерево

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

Входные данные

Содержит описание дерева. Первая строка содержит количество его вершин n (2n50000). Каждая из следующих (n - 1) строк содержит описание ребер дерева. Каждое ребро задается тремя положительными целыми числами. Первые два числа - номера вершин, которые соединяет ребро, от 1 до n, третье число - длина ребра. Общая длина всех ребер не превосходит 231 - 1. Гарантируется, что входное дерево корректно.

Выходные данные

Содержит в точности n строк: k-ая строка содержит расстояние от вершины k (k = 1..n) до самой дальней вершины.

Лимит времени 1 секунда
Лимит использования памяти 122.49 MiB
Входные данные #1
6
1 5 3
2 6 3
6 1 1
1 3 5
4 6 4
Выходные данные #1
5
9
10
10
8
6
Источник ACM ICPC SEERC-2012, 13.10.2012 Bucharest, Vinnica