题目理解

我们有一个无向图，$K$ 个人轮流进行操作：

• 第 $1$ 个人：删除当前图的一个最大生成森林
• 第 $2$ 个人：在剩余图中删除一个最大生成森林
• ...
• 第 $K$ 个人：在剩余图中删除一个最大生成森林

对于每条边，我们需要求出它被哪个人删除，如果没有被删除则输出 $0$。

关键点：

• 最大生成森林：即最大生成树（如果图连通）或最大生成树的森林
• 边权互不相同，保证了最大生成森林的唯一性
• 每个人删除的是当前剩余图中的最大生成森林

关键观察

1. 经典结论

在边权互不相同的情况下，一条边会出现在原图的第 $i$ 个最大生成森林中，当且仅当它在原图的最大生成森林中，并且是第 $i$ 重要的边。

更准确地说：如果我们按边权从大到小排序，那么：

• 第 $1$ 个人会取走所有不会形成环的边（即最大生成森林）
• 第 $2$ 个人会取走剩下的边中不会形成环的边
• 依此类推...

2. 问题转化

这等价于：对原图的所有边，按边权从大到小排序，然后模拟 $K$ 次 Kruskal 算法。

具体来说：

1. 将边按权值从大到小排序
2. 用并查集维护连通性
3. 对于每条边，找到它第一次能被加入生成森林的时刻（即它连接的两个点第一次不连通的时刻）

3. 算法思路

对于每条边 $e = (u, v)$，设它在排序后的位置为 $i$：

• 如果 $u$ 和 $v$ 在考虑前 $i-1$ 条边时已经连通，那么这条边会在第 $j$ 轮被删除，其中 $j$ 是使得 $u$ 和 $v$ 在第 $j$ 轮开始时不再连通的轮数
• 如果 $u$ 和 $v$ 在考虑前 $i-1$ 条边时不连通，那么这条边会在第 $1$ 轮被删除

高效解法

1. 离线处理

我们可以离线处理所有边：

1. 将边按权值从大到小排序
2. 用并查集维护连通分量，但记录每个连通分量的"删除时间"
3. 对于每条边，通过并查集找到它所属的连通分量的删除时间

2. 并查集维护删除时间

在并查集中，我们不仅维护父节点信息，还维护：

• min_time[x]：以 $x$ 为根的连通分量中，所有边的最早删除时间
• 当合并两个连通分量时，min_time 取两者中的较小值

3. 具体步骤

1. 初始化并查集，每个点的 min_time 为 $K+1$（表示还没有被删除）
2. 按边权从大到小处理每条边 $e = (u, v)$：
   • 找到 $u$ 和 $v$ 的根节点 ru 和 rv
   • 如果 ru == rv：说明这条边会形成环，它的删除时间就是 min_time[ru]
   • 如果 ru != rv：说明这条边可以被加入，它的删除时间是 min(min_time[ru], min_time[rv])，然后合并两个连通分量，新的 min_time 为两者中的较小值

总结

这道题的关键在于理解：

1. 最大生成森林的性质：边权互不同时，最大生成森林唯一
2. 多轮删除的过程：相当于多次执行 Kruskal 算法
3. 环边与树边：非树边会在第一轮被删除，树边会在后续轮次被删除