F - MST Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

頂点に 1 から N の番号が、辺に 1 から N-1 の番号が付いた N 頂点 N-1 辺の重み付き無向連結グラフ G が与えられます。辺 i は頂点 a_i と頂点 b_i を結んでおり、その重みは c_i です。

Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。

  • 整数 u_i,v_i,w_i が与えられる。G の頂点 u_i,v_i の間に重み w_i の辺を追加する。その後、G の最小全域木に含まれる辺の重みの和を出力する。

制約

  • 2\leq N\leq 2 \times 10^5
  • 1\leq Q\leq 2 \times 10^5
  • 1\leq a_i\lt b_i\leq N
  • 1\leq u_i\lt 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

Score : 550 points

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