最小生成树查询

题目描述

给定一个有 $N$ 个顶点、$N-1$ 条边的带权无向连通图 $G$，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，权重为 $c_i$。

你需要按顺序处理 $Q$ 个查询。第 $i$ 个查询描述如下：

给定整数 $u_i, v_i, w_i$。在 $G$ 中顶点 $u_i$ 和 $v_i$ 之间添加一条权重为 $w_i$ 的边。然后，输出 $G$ 的最小生成树的边权和。

输入格式

输入按以下格式从标准输入给出：

$N$ $Q$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$ $c_{N-1}$
$u_1$ $v_1$ $w_1$
$\vdots$
$u_Q$ $v_Q$ $w_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

样例

4 4
1 2 6
2 3 5
2 4 4
1 3 3
1 2 3
1 4 10
3 4 1

12
10
10
7

8 6
1 8 8
1 6 10
1 5 8
2 6 6
6 7 6
1 3 9
2 4 7
1 3 4
1 6 7
3 4 6
1 5 1
7 8 4
3 5 3

49
46
45
38
34
33

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $1 \le a_i \lt b_i \le N$
• $1 \le u_i \lt v_i \le N$
• $1 \le c_i, w_i \le 10$
• 处理查询前图 $G$ 是连通的
• 所有输入值均为整数