F - 丰富的树

得分：$600$ 分

问题描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。 树上的第 $i$ 条边连接 Vertex $a_i$ 和 Vertex $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$ 的边现在恢复了原始长度。