AT_abc187_e [ABC187E] Through Path

[problemUrl]: https://atcoder.jp/contests/abc187/tasks/abc187_e $ N $ 頂点 $ N-1 $ 辺から成る木があり、頂点には $ 1,\ 2,\ \dots,\ N $ の番号が、辺には $ 1,\ 2,\ \dots,\ N-1 $ の番号がついています。辺 $ i $ は頂点 $ a_i $ と頂点 $ b_i $ を結びます。 この木の各頂点には $ 1 $ つの整数が書かれています。頂点 $ i $ に書かれている整数を $ c_i $ とします。はじめ、 $ c_i\ =\ 0 $ です。 $ Q $ 個のクエリが与えられます。 $ i $ 番目のクエリでは、整数 $ t_i,\ e_i,\ x_i $ が与えられます。クエリの内容は以下の通りです。 - $ t_i\ =\ 1 $ のとき : 頂点 $ a_{e_i} $ から辺をたどって頂点 $ b_{e_i} $ を通らずに到達できるような全ての頂点 $ v $ に対して、$ c_v $ を $ c_v\ +\ x_i $ に書き換える。 - $ t_i\ =\ 2 $ のとき : 頂点 $ b_{e_i} $ から辺をたどって頂点 $ a_{e_i} $ を通らずに到達できるような全ての頂点 $ v $ に対して、$ c_v $ を $ c_v\ +\ x_i $ に書き換える。 すべてのクエリを処理した後、各頂点に書かれた整数を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $ $ Q $ $ t_1 $ $ e_1 $ $ x_1 $ $ \vdots $ $ t_Q $ $ e_Q $ $ x_Q $

すべてのクエリを処理した後の $ c_1,\ c_2,\ \dots,\ c_N $ をこの順に改行区切りで出力せよ。

### 制約 - 入力は全て整数 - $ 2\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ a_i,\ b_i\ \le\ N $ - 与えられるグラフは木である - $ 1\ \le\ Q\ \le\ 2\ \times\ 10^5 $ - $ t_i\ \in\ \{1,\ 2\} $ - $ 1\ \le\ e_i\ \le\ N-1 $ - $ 1\ \le\ x_i\ \le\ 10^9 $ ### Sample Explanation 1 $ 1 $ 番目のクエリでは、頂点 $ 1 $ から始めて頂点 $ 2 $ を通らずに到達できる頂点 $ 1 $ に $ 1 $ を足します。 $ 2 $ 番目のクエリでは、頂点 $ 4 $ から始めて頂点 $ 5 $ を通らずに到達できる頂点 $ 1,\ 2,\ 3,\ 4 $ に $ 10 $ を足します。 $ 3 $ 番目のクエリでは、頂点 $ 2 $ から始めて頂点 $ 1 $ を通らずに到達できる頂点 $ 2,\ 3,\ 4,\ 5 $ に $ 100 $ を足します。 $ 4 $ 番目のクエリでは、頂点 $ 3 $ から始めて頂点 $ 2 $ を通らずに到達できる頂点 $ 3 $ に $ 1000 $ を足します。