题目描述

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

题目大意

有一个 $N$ 个节点的树，每条边有颜色、边权。

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

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

この入力中のグラフは次のようなものです。  ここで、色 $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$ の辺の長さが元に戻っていることに注意してください。