🟩 Kruskal-5 🏫《动态校区合并》

（在线加边 + 查询当前最小生成森林 MSF 的总权值 & 连通块数）

🧩 题目背景（兔猫信奥学院）

兔猫信奥学院在全国有许多分散校区。加菲老师每天都会收到一条“候选道路”消息：某两个校区之间可以修一条路，造价为 $w$。 道路会不断新增，小兔和小猫需要实时回答：

如果只在每个连通校区内部选一些路，使得“能连通且不成环”，并且总造价最小（也就是最小生成森林 MSF），那么此刻： 1）共有多少个互不连通的校区块（连通块）？ 2）最小生成森林的总造价是多少？

📌 题目描述

给定 $n$ 个点（校区）编号 $1..n$，按顺序处理 $m$ 条操作，操作有两种：

• A u v w：新增一条无向边 $(u,v)$，权值为 $w$（允许重边；允许自环）。

• Q：询问当前图的：

  • cc：连通块个数
  • sum：当前图的最小生成森林总权值（把每个连通块内部做 MST，然后把这些 MST 权值相加）

输出每次 Q 的 cc sum。

注意：

• 自环 $(u=u)$ 对 MSF 没有帮助，应被忽略（但它仍然“存在于图中”，只是不会被 MSF 选用）。
• 图可能一直不连通，因此我们做的是 MSF 而不是要求整图 MST。

✅ 输入格式

第一行两个整数 $n,m$。 接下来 $m$ 行，每行是一个操作 A ... 或 Q。

✅ 输出格式

对每个 Q，输出一行：cc sum。

4 8
Q
A 1 2 10
A 2 3 5
Q
A 1 3 1
Q
A 4 4 7
Q

4 0
2 15
2 6
2 6

解释：

• 初始 4 个点都孤立：cc=4，MSF 不选边，sum=0
• 加入 1-2(10)、2-3(5)：此时 {1,2,3} 连通、{4} 孤立，cc=2，MSF 选这两条边，sum=15
• 再加入 1-3(1)：会形成环，但可以用 1 替换掉路径上最贵的 10，使 MSF 更小：sum=11
• 加入自环 4-4(7)：自环永远不会进入 MSF，所以答案不变。

5 7
A 1 2 3
A 4 5 8
Q
A 2 3 4
Q
A 3 1 1
Q

3 11
2 15
2 12

解释：

• 前两条边形成 {1,2} 与 {4,5}，还有 {3}：cc=3，MSF 权值 3+8=11
• 加入 2-3(4) 后 {1,2,3} 连通：cc=2，MSF 3+4+8=15
• 加入 3-1(1) 后可替换掉 {1,2,3} 里较贵边，使 MSF 变小：sum=12

📏 数据范围

• $1 \le n \le 2\times 10^5$
• $1 \le m \le 3\times 10^5$
• $1 \le w \le 10^9$
• 允许重边、自环
• 操作在线，需高效处理