Задача №114222. Сумма длин путей 2
Дано дерево на \(n\) вершинах. На каждом ребре написан его вес. Требуется для каждого \(v\) посчитать сумму взвешенных длин всех путей в данном дереве, исходящих из \(v\). Пути \(\langle v, u \rangle\) и \(\langle u, v \rangle\) считаются различными.
Входные данные
Первая строка каждого теста содержит натуральное число \(n\) — количество вершин в дереве (\(1 \leq n \leq 100\,000\)). Следующие \(n - 1\) строк содержат по \(3\) натуральных числа \(v, u, w\) и описывают ребро дерева, соединяющее две вершины \(v\) и \(u\) и имеющее вес \(w\) (\(1 \leq v, u \leq n\), \(0 \leq w \leq 10^6\)).
Выходные данные
Выведите \(n\) чисел — требуемое в условии.
Примеры
Входные данные
3 1 2 1 1 3 3
Выходные данные
4 5 7
Сдать: для сдачи задач необходимо войти в систему