AT_abc133_f [ABC133F] Colorful Tree

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $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_2$ $b_2$ $c_2$ $d_2$ > $\vdots$ > $a_{N-1}$ $b_{N-1}$ $c_{N-1}$ $d_{N-1}$ > $x_1$ $y_1$ $u_1$ $v_1$ > $x_2$ $y_2$ $u_2$ $v_2$ > $\vdots$ > $x_Q$ $y_Q$ $u_Q$ $v_Q$

输出 $Q$ 行，第 $j$ 行输出第 $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$ - 给定的图是一棵树。 - 输入中的所有值均为整数。 ### 样例解释 1 输入中的图如下所示。  其中，颜色 $1$ 的边用红色实线表示，颜色 $2$ 的边用绿色粗线表示，颜色 $4$ 的边用蓝色虚线表示。 - 询问 1：假设所有颜色为 $1$ 的边的长度都变为 $100$，则顶点 $1$ 和 $4$ 之间的距离为 $100 + 30 = 130$。 - 询问 2：假设所有颜色为 $1$ 的边的长度都变为 $100$，则顶点 $1$ 和 $5$ 之间的距离为 $100 + 100 = 200$。 - 询问 3：假设所有颜色为 $3$ 的边的长度都变为 $1000$（但实际上不存在颜色为 $3$ 的边），则顶点 $3$ 和 $4$ 之间的距离为 $20 + 10 + 30 = 60$。注意在本次询问后，颜色 $1$ 的边长度已恢复为原值。 由 ChatGPT 4.1 翻译