配点 : $600$ 点

問題文

$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$ 間の距離を求めよ。(辺の長さの変更はこれ以降の問いには影響しない。)

制約

• $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$
• 与えられるグラフは木である。
• 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

$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

この入力中のグラフは次のようなものです。

ここで、色 $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$ の辺の長さが元に戻っていることに注意してください。