[ABC133F] Colorful Tree

有一个 $N$ 个节点的树，每条边有颜色、边权。 您需要处理 $Q$ 个询问，每个询问给出 $x_i,y_i,u_i,v_i$，您需要求出**假定**所有颜色为 $x_i$ 的边边权全部变成 $y_i$ 后，$u_i$ 和 $v_i$ 之间的距离。**询问之间互相独立。**

[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 $ への回答を出力すること。

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4

130
200
60

### 制約 - $ 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\ <\ v_j\ \leq\ N $ - 与えられるグラフは木である。 - 入力中のすべての値は整数である。 ### Sample Explanation 1 この入力中のグラフは次のようなものです。 !\[図\](https://img.atcoder.jp/ghi/ca75688b08f73eb63a30ce6daa54a781.png) ここで、色 $ 1 $ の辺は赤い実線で、色 $ 2 $ の辺は緑の太線で、色 $ 4 $ の辺は青い破線で示されています。 - 問 $ 1 $: 色 $ 1 $ のすべての辺の長さが $ 100 $ に変更されたと仮定すると、頂点 $ 1,\ 4 $ 間の距離は $ 100\ +\ 30\ =\ 130 $ です。 - 問 $ 2 $: 色 $ 1 $ のすべての辺の長さが $ 100 $ に変更されたと仮定すると、頂点 $ 1,\ 5 $ 間の距離は $ 100\ +\ 100\ =\ 200 $ です。 - 問 $ 3 $: 色 $ 3 $ のすべての辺の長さが $ 1000 $ に変更されたと仮定すると (そのような辺は存在しません)、頂点 $ 3,\ 4 $ 間の距離は $ 20\ +\ 10\ +\ 30\ =\ 60 $ です。この問いでは色 $ 1 $ の辺の長さが元に戻っていることに注意してください。