问题分析

本题是一道基于带权并查集（Union-Find with Weights） 的字符串编码问题，核心任务是为每个节点生成一个独特的编码，该编码由连接节点的操作序号组成。通过分析代码可知，算法利用并查集维护节点间的连接关系，并通过标签（Tag）记录编码的生成规则，最终输出每个节点的编码值。

算法思路

1. 数据结构设计

• 并查集数组：fa[x] 存储节点 x 的父节点，用于维护连通分量。
• 标签结构：Tag 包含两个参数：
  • multg：乘法因子（用于编码的位数扩展）
  • addtg：加法项（用于记录操作序号）
  • 标签的合并规则：tag1 += tag2 等价于：$$\text{multg} = (\text{tag1.multg} \times \text{tag2.multg}) \mod \text{MOD} $$$$\text{addtg} = (\text{tag1.addtg} \times \text{tag2.multg} + \text{tag2.addtg}) \mod \text{MOD} $$

2. 核心操作

• 查找根节点（getrt函数）：

  • 递归查找节点的根节点，同时进行路径压缩。
  • 路径压缩时，合并沿途节点的标签（ans[x] += ans[fx]），确保编码信息正确传递。
  • 时间复杂度接近 $O(1)$（带路径压缩的并查集）。

• 合并操作：

  • 对于第 i 次操作（连接节点 u 和 v）：
    1. 查找 u 和 v 的根节点 fu 和 fv。
    2. 若已连通，跳过本次操作。
    3. 否则，创建新节点 tot 作为 fu 和 fv 的父节点。
    4. 更新 fu 和 fv 的标签：
       • ans[fu].multg = (ans[fv].multg × 10) mod MOD（编码左移一位，即乘以10）
       • ans[fu].addtg = (ans[fv].addtg + ans[fv].multg × i) mod MOD（添加当前操作序号 i 作为新的末位）
       • ans[fv] 对称更新（确保 u 和 v 的编码分别以 i 结尾且长度一致）。

3. 编码生成

• 每个节点的编码通过标签 addtg 记录，其生成规则为：
  • 初始状态：ans[i].multg = 1，ans[i].addtg = 0（未参与任何连接时编码为空）。
  • 每参与一次连接操作 i，编码在原有基础上左移一位（乘以10）并添加 i 作为末位，即：$$\text{新编码} = \text{旧编码} \times 10 + i$$
  • 最终编码通过路径压缩后的 addtg 直接获取。

4. 结果输出

• 对每个节点 i 执行 getrt(i) 确保路径压缩完成，标签信息更新至最新。
• 输出 ans[i].addtg 作为节点 i 的最终编码（模 $10^9 + 7$）。

关键公式与复杂度

1. 标签合并公式：

   $$\text{multg} = (m_1 \times m_2) \mod \text{MOD}$$ $$\text{addtg} = (a_1 \times m_2 + a_2) \mod \text{MOD} $$

   其中 $(m_1, a_1)$ 和 $(m_2, a_2)$ 是两个标签的参数，模拟编码的拼接操作。

2. 编码更新公式： 连接操作 i 时，编码更新为：

   $$\text{new\_code} = (\text{old\_code} \times 10 + i) \mod \text{MOD} $$

   确保编码以操作序号为字符，按连接顺序生成。

3. 时间复杂度：

   • 并查集的查找和合并操作均为 $O(\alpha(n))$（$\alpha$ 为阿克曼函数的反函数，近似常数）。
   • 总时间复杂度为 $O(m \alpha(n) + n)$，其中 $m$ 是操作数，$n$ 是节点数，适合处理 $n, m \leq 2 \times 10^5$ 的数据规模。

代码解析

算法的核心是通过带权并查集维护节点间的编码关系，利用标签的乘法和加法项模拟编码的拼接过程，在高效处理连接操作的同时，确保每个节点的编码唯一且符合操作顺序。