Colorful Tree

题目描述

有一棵由 $1$ 到 $N$ 编号的 $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_{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

提示

$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$ 的边用实心红线表示，颜色为 $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$ 的边此时仍为它们的原始长度。

标签: AtCoder|abc133F

来源

AtCoder|abc133F