AT_nikkei2019_2_final_g Road Trip

[problemUrl]: https://atcoder.jp/contests/nikkei2019-2-final/tasks/nikkei2019_2_final_g $ N $ 頂点の無向木があり、頂点には $ 1 $ から $ N $ の、辺には $ 1 $ から $ N-1 $ の番号がついています。辺 $ i $ は 頂点 $ A_i $ と 頂点 $ B_i $ を結んでおり、$ C_i $ の重みを持ちます。重みの値は負である可能性もあることに注意してください。 この木の連結な部分グラフを「運転部分木」と呼び、特に頂点 $ u $ と頂点 $ v $ を含むものを「$ u-v $ 運転部分木」とします。ある運転部分木が持つ辺の重みの合計を、その運転部分木の「楽しさ」とします。 $ Q $ 個の整数組 $ (U_i,\ V_i) $ が与えられるので、各 $ i $ に対して次の質問に答えてください。 - $ U_i-V_i $ 運転部分木の楽しさとしてあり得る最大値は何か。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ A_1 $ $ B_1 $ $ C_1 $ : $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $ $ Q $ $ U_1 $ $ V_1 $ : $ U_Q $ $ V_Q $

$ Q $ 行出力してください。$ i $ 行目には、$ U_i-V_i $ 運転部分木の楽しさとしてあり得る最大値を出力してください。

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