分数: 550 点
问题陈述
给你一个加权无向连通图 G 与 N 顶点和 N-1 边,其中顶点编号 1 to N 和边已编号 1 to N-1。边缘 i 连接顶点 a_i 和 b_i 重量为 c_i.
你被给予 Q 查询按顺序处理。的 i第查询描述如下:
- 给你整数 u_i, v_i, w_i。添加带有权重的边 w_i 顶点之间 u_i 和 v_i in G。然后,打印最小生成树中边的权重之和 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