彩色树

题目描述

有一棵具有 $N$ 个顶点、编号为 $1$ 到 $N$ 的树。

这棵树的第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$,它的颜色是 $c_i$,长度是 $d_i$。这里,每条边的颜色用 $1$ 到 $N-1$ 之间的整数表示,相同的整数对应同一种颜色,不同的整数对应不同的颜色。

请回答下面的 $Q$ 个问题。

• 问题 $j$ ($1 \le j \le 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 \le j \le 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$ 的边长度已经恢复原状。

数据范围

• $2 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le a_i, b_i \le N$
• $1 \le c_i \le N-1$
• $1 \le d_i \le 10^4$
• $1 \le x_j \le N-1$
• $1 \le y_j \le 10^4$
• $1 \le u_j \lt v_j \le N$
• 给定的图是一棵树
• 输入中的所有值都是整数