← 返回题目
题库练习 [ABC133F] Colorful Tree
← 上一题 下一题 →

A7632 | [ABC133F] Colorful Tree

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

有一棵包含 $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$ 个询问的答案。

输入输出样例

输入 #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
C++ 编辑器
输入
输出