题意理解

我们有一个包含 $n$ 个节点的图（$n$ 可达 $10^{18}$），初始有 $b$ 条边，然后进行 $a$ 次操作。每次操作给所有编号差为 $d_i$ 的节点对添加一条权值为 $x_i$ 的边。最终需要计算所有连通分量的最小生成树权重之和。

关键挑战：

• $n$ 极大，无法显式存储所有节点和边
• 需要利用图的特殊结构设计高效算法

核心思路

关键观察 1：等差边的图论结构

对于差值为 $d$ 的边操作，这些边实际上构成了一个循环图：节点 $i$ 与节点 $i+d \bmod n$ 相连。

这样的图可以分解为 $\gcd(n, d)$ 个连通分量，每个分量是一个环或路径。

关键观察 2：问题分解

原问题可以分解为：

1. 分析每次操作产生的连通分量
2. 在各自连通分量内计算最小生成树
3. 合并不同操作产生的边

关键观察 3：整体二分框架

由于 $n$ 极大但操作数 $a+b$ 相对较小，可以使用整体二分：

• 将所有边（初始边 + 操作边）按边权排序
• 使用分治策略批量处理边权区间
• 在每层递归中，用并查集维护连通性

算法框架

方法一：基于同余类的分析

核心思想：利用数论性质分析连通性

对于差值为 $d$ 的操作：

• 图会分解为 $\gcd(n, d)$ 个连通分量
• 每个分量包含所有满足 $i \equiv r \pmod{\gcd(n, d)}$ 的节点
• 在每个分量内，边形成一个环或路径

最小生成树计算：

• 环：需要删除一条最大边
• 路径：本身就是树

方法二：整体二分实现

算法步骤：

1. 收集所有边（初始边 + 操作产生的边）
2. 对边权范围 $[L, R]$ 进行整体二分：
   • 处理边权 $\leq mid$ 的边，用并查集维护连通性
   • 递归处理左右两半
3. 在递归过程中累计最小生成树权重

关键技术：

• 并查集回滚：支持递归回溯
• 边权离散化：处理大范围边权
• 连通分量跟踪：维护每个分量的生成树信息

方法三：操作合并优化

由于操作是有顺序的，可以：

• 合并相同的 $d_i$ 操作（取最小 $x_i$）
• 分析操作之间的相互作用
• 利用单调性减少计算量

复杂度分析

• 整体二分：$O((a+b) \log W \cdot \alpha(n))$，其中 $W$ 是边权范围
• 并查集操作：每个边被处理 $O(\log W)$ 次
• 空间复杂度：$O(a+b)$

在 $a, b \leq 5 \times 10^4$ 时可行。

实现细节

并查集设计

需要支持：

• 连通性查询：判断两个节点是否连通
• 分量大小：计算连通分量大小
• 回滚操作：支持递归回溯

边权处理

由于 $n$ 极大，不能显式存储所有边，而是：

• 存储边权的生成函数
• 利用数论性质批量计算
• 在模 $998244353$ 下运算

特殊情况处理

1. $d_i = 0$：自环，可忽略
2. 重复边：取最小边权
3. 大 $n$ 处理：使用数学公式而非显式枚举

总结

本题的核心在于：

1. 问题转化：将超大规模图问题转化为可计算的形式
2. 数论应用：利用同余理论分析图结构
3. 算法选择：整体二分处理大规模排序问题
4. 数据结构：并查集维护动态连通性

这是一个典型的理论计算机科学难题，考察选手将数学洞察与算法设计相结合的能力，符合集训队互测的高标准要求。