[ACM 題目] 樹形鎖頭

contents

1. 1. Problem
   1. 1.1. Background
   2. 1.2. Problem
2. 2. Input
3. 3. Output
4. 4. Sample Input
5. 5. Sample Output
6. 6. Solution

Problem

Background

正值大四的 Morris，面臨無法畢業的窘境，每天不是玩 PoE 遊戲就是在解題目，為了逃避現實解題目也越來越多，但對於未來目標仍然沒有任何進展，一個人在房間裡孤拎拎地打著 PoE，萬萬沒想到遊戲帳號被盜取，「密碼鎖什麼的果然太天真的，ACM 鎖才是未來的目標」打密碼登入有什麼了不起的，寫程式 AC 登入才有意思。

Problem

一張無向圖，給 N 個點、N - 1 條邊，任兩點之間只會有一條路徑。

操作 (u, v, k)：將 u, v 之間經過的節點權重加上 k。

請問經過 M 次操作後，每個節點的權重值為何？

Input

輸入有多組測資。

每一組測資第一行 會有兩個正整數 N, M (0 < N, M < 32767)，接下來會有 N - 1 行，每行上會有兩個整數 u, v (0 <= u, v < N) 表示 u 和 v 之間有一條邊。接著會有 M 行操作 (u, v, k) (0 < k < 32767)。

Output

每組測資輸出一行，分別將節點權重輸出。

Sample Input

7 4
0 1
0 2
1 3
1 4
2 5
2 6
2 3 1
3 4 2
0 5 4
6 6 8

Sample Output

5 3 5 3 2 4 8

Solution