← 返回题目列表

AtCoder · abc133_f

F. 七彩树

中文机器翻译题面 查看原题

分数: 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

该输入中的图表如下:

Figure

这里是颜色的边缘 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 现在有了原来的长度。