题目描述

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

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

输入格式

第一行两个整数 $N, Q$。

接下来 $N - 1$ 行，每行四个整数 $a_i, b_i, c_i, d_i$，表示$a_i$ 和 $b_i$ 之间存在一条边，颜色为 $c_i$，边权为 $d_i$。

接下来 $Q$ 行，每行四个整数 $x_i, y_i, u_i, v_i$，含义如题所述。

$2 \le N \le 10^5$，$1 \le Q \le 10^5$，$1 \le d_i, y_i \le 10^4$，$1 \le c_i, x_i \le N - 1$。

输出格式

$Q$ 行，每个询问输出一行表示答案。

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$ 的边的边权改成 $100$ 之后，$1$ 号点到 $4$ 号点之间的距离则变成 $100 + 30 = 130$。
• 第二个询问：颜色 $1$ 的边的边权改成 $100$ 之后，$1$ 号点到 $5$ 号点的距离则变成 $100 + 100 = 200$。
• 第三个询问：颜色 $3$ 的边的边权改成 $1000$ 之后，这棵树没有什么变化，因为没有颜色为 $3$ 的边，所以 $3$ 号点到 $4$ 号点之间的距离为 $20 + 10 + 20 = 60$。