分数: 600 点
问题陈述
有一棵树 N 顶点编号 1 to 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。 (边长的变化不影响后续查询。)
约束
- 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.
示例输入 1
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
示例输出 1
130 200 60
该输入中的图表如下:

这里是颜色的边缘 1 显示为红色实线,颜色的边缘 2 显示为粗绿线,颜色的边缘 4 显示为蓝色虚线。
- 查询 1:假设颜色为的每条边的长度 1 更改为 100,顶点之间的距离 1 和顶点 4 is 100 + 30 = 130.
- 查询 2:假设颜色为的每条边的长度 1 更改为 100,顶点之间的距离 1 和顶点 5 is 100 + 100 = 200.
- 查询 3:假设颜色为的每条边的长度 3 更改为 1000 (没有这条边),Vertex之间的距离 3 和顶点 4 is 20 + 10 + 30 = 60。注意颜色的边缘 1 现在有了原来的长度。