AT_abc133_f [ABC133F] Colorful Tree

[problemUrl]: https://atcoder.jp/contests/abc133/tasks/abc133_f $ 1 $ から $ N $ までの番号がつけられた $ N $ 個の頂点を持つ木があります。 この木の $ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結び、その色は $ c_i $、長さは $ d_i $ です。 ここで各辺の色は $ 1 $ 以上 $ N-1 $ 以下の整数で表されており、同じ整数は同じ色に、異なる整数は異なる色に対応します。 以下の $ Q $ 個の問いに答えてください。 - 問 $ j $ ($ 1\ \leq\ j\ \leq\ Q $): 色 $ x_j $ のすべての辺の長さが $ y_j $ に変更されたと仮定して、二頂点 $ u_j,\ v_j $ 間の距離を求めよ。(辺の長さの変更はこれ以降の問いには影響しない。)

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ a_1 $ $ b_1 $ $ c_1 $ $ d_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $ $ c_{N-1} $ $ d_{N-1} $ $ x_1 $ $ y_1 $ $ u_1 $ $ v_1 $ $ : $ $ x_Q $ $ y_Q $ $ u_Q $ $ v_Q $

$ Q $ 行出力せよ。$ j $ 行目 ($ 1\ \leq\ j\ \leq\ Q $) に問 $ j $ への回答を出力すること。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ N $ - $ 1\ \leq\ c_i\ \leq\ N-1 $ - $ 1\ \leq\ d_i\ \leq\ 10^4 $ - $ 1\ \leq\ x_j\ \leq\ N-1 $ - $ 1\ \leq\ y_j\ \leq\ 10^4 $ - $ 1\ \leq\ u_j\