Задачи
Отчет энергии молнии
Отчет энергии молнии
В городе Гром находится много домов, и все они работают на молнии. Два дома могут быть соединены между собой проводом. Провода соединяют дома таким образом, что всегда имеется только один путь из одного дома в другой. Каждый дом имеет большую батарею, которая может хранить бесконечное количество электрической энергии.
Каждый день несколько молний ударяют в некоторые дома. Эти молнии достаточно необыкновенные. При ударе молния одновременно попадает в два дома: в один дом (\textbf{A}) попадает красная молния, а в другой дом (\textbf{B}) синяя молния. После удара каждый дом на пути от \textbf{A} до \textbf{B} (включительно) получает некоторое количество электрической энергии, которая добавляется к батарее дома.
Мэр города Гром хочет получить отчет о хранящейся электрической энергии в каждом доме в конце месяца, так как владелец каждого дома должен заплатить за полученную энергию налоги. Чтобы не допустить владельцам сообщать неправильные данные об энергии, запасенной в батарее их дома (так как жители хотят платить меньше налогов), Вас просят составить правильный отчет на основе наблюдения за молниями на протяжении месяца. В начале месяца энергия на батарее каждого дома равнялась \textbf{0}.
\InputFile
Первая строка содержит количество тестов \textbf{T} (\textbf{T}\textit{ ≤} \textbf{10}). Каждый тест начинается целым числом \textbf{N} (\textbf{2}\textit{ ≤ }\textbf{N}\textit{ ≤ }\textbf{50, 000}) - количеством домов в городе Гром. Следующие \textbf{N - 1} строк содержат информацию о соединении домов проводами: каждая строка содержит два целых числа \textbf{X} и \textbf{Y}, обозначающих, что дом \textbf{X} соединен с домом \textbf{Y}. Дома пронумерованы числами от \textbf{0} до \textbf{N - 1}. Следующая строка содержит количество ударов молнии \textbf{Q} (\textbf{1}\textit{ ≤ }\textbf{Q}\textit{ ≤ }\textbf{50, 000}). Следующие \textbf{Q} строк описывают необычные удары молнии, которые имеют место каждый месяц. Каждая строка содержит три целых числа \textbf{A}, \textbf{B}, \textbf{C}, означающих, что красная молния попадает в дом \textbf{A}, синяя молния в дом \textbf{B}, передаваемая мощность энергии равна \textbf{C} (не более \textbf{100}), которая вычисляется специальными приборами.
\OutputFile
Для каждого теста вывести "\textbf{Case #X:}" (без кавычек), где \textbf{X} означает номер теста, а также \textbf{N} строк, описывающих электрическую энергию батарей всех домов от номера \textbf{0} до \textbf{N - 1} в конце каждого месяца.
Входные данные #1
1 9 0 1 1 2 2 3 2 4 2 7 7 8 7 6 6 5 5 1 4 10 3 5 3 0 8 5 1 6 10 4 4 100
Выходные данные #1
Case #1: 5 25 28 3 110 3 13 18 5