ABC 355_F MST Query

题目描述

给你一个有N个顶点和−1条边的加权无向连通图G，其中顶点的编号为1到N，边的编号为1到N−1。连接顶点ai​和bi​的边的权重为ci​。

给您Q个查询，请按顺序处理。i-th查询的描述如下：

• 给您整数ui​,vi​,wi​。在G中的顶点ui​和vi​之间添加一条权重为wi​的边。然后，打印G最小生成树中各条边的权重之和。

输入描述

输入内容由标准输入法提供，格式如下

N 
1​ 1​ 1​
⋮
−1​ −1​ −1​
1​ 1 1​
⋮⋮
​ ​ ​

• 2≤N≤2×10^5
• 1≤Q≤2×10^5
• 1≤ai​<bi​≤N
• 1≤ui​<vi​≤N
• 1≤ci​,wi​≤10
• 在处理查询之前，图已经连接。
• 所有输入值均为整数。

输出描述

打印行。-th 行应包含-th 查询的答案。

提示

样例1：

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