Задачі
Звіт енергії блискавки
Звіт енергії блискавки
У місті Грім знаходиться багато будинків, і всі вони працюють від блискавок. Два будинки можуть бути з'єднані між собою дротом. Дріт сполучає будинки таким чином, що завжди існує лише один шлях з одного будинку до іншого. Кожен будинок має велику батарею, яка може зберігати нескінченну кількість електричної енергії.
Кожен день кілька блискавок влучають у деякі будинки. Ці блискавки досить незвичайні. При ударі блискавка одночасно потрапляє в два будинки: в один будинок (\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