103555: [Atcoder]ABC355 F - MST Query

Problem Statement

You are given a weighted undirected connected graph $G$ with $N$ vertices and $N-1$ edges, where vertices are numbered $1$ to $N$ and edges are numbered $1$ to $N-1$. Edge $i$ connects vertices $a_i$ and $b_i$ with a weight of $c_i$.

You are given $Q$ queries to process sequentially. The $i$-th query is described as follows:

• You are given integers $u_i, v_i, w_i$. Add an edge with weight $w_i$ between vertices $u_i$ and $v_i$ in $G$. Then, print the sum of the weights of the edges in a minimum spanning tree of $G$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• $1 \leq u_i < v_i \leq N$
• $1 \leq c_i, w_i \leq 10$
• The graph is connected before processing the queries.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

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

Sample Output 1

12
10
10
7

Here is the graph after adding the edge for each query. The edges included in the minimum spanning tree are colored red.

Sample Input 2

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

Sample Output 2

49
46
45
38
34
33

问题描述

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

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

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

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• $1 \leq u_i < v_i \leq N$
• $1 \leq c_i, w_i \leq 10$
• 在处理查询之前，图是连通的。
• 所有输入值都是整数。

输入

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

$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$ 个查询的答案。

样例输入 1

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

样例输出 1

12
10
10
7

这是在每个查询后添加边的图。最小生成树包含的边用红色标出。

样例输入 2

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

样例输出 2

49
46
45
38
34
33