AT_nikkei2019_final_g Greatest Journey

[problemUrl]: https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_g $ N $ 頂点の木があり、頂点には $ 1 $ から $ N $ までの番号が、辺には $ 1 $ から $ N-1 $ までの番号がついています。 辺 $ i $ は頂点 $ A_i $ と $ B_i $ を結ぶ辺です。 $ 1 $ から $ M $ までの番号のついた $ M $ 人の人が、今からこの木の上を移動します。 人 $ i $ は、頂点 $ V_i $ から出発し、以下の操作をちょうど $ L_i $ 回行います。 - 今いる頂点に繋がっている辺を自由に一つ選び、その辺を通って隣の頂点へ移動する。 このとき、通った辺の番号が $ x $ なら、$ C_x $ 点を得る。 すべての $ i $ について、人 $ i $ が $ L_i $ 回の操作で得られる得点の総和の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $ $ M $ $ V_1 $ $ L_1 $ $ V_2 $ $ L_2 $ $ \vdots $ $ V_M $ $ L_M $

$ M $ 行出力せよ。 $ i $ 行目には、人 $ i $ が $ L_i $ 回の操作で得られる得点の総和の最大値を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ A_i\