题目分析

问题本质

在动态删边的图中，维护从节点1出发的连通性，计算每个节点在GC操作中被回收的时间，最终求出所有节点的内存占用时间加权和。

核心矛盾

• 正向操作困难：删除边和GC操作使得连通性不断变化
• 数据规模大：$n, m, q \leq 4 \times 10^5$，需要高效算法
• GC语义特殊：只回收无法从节点1访问到的节点

关键观察

逆向思维转化

核心洞察：如果从最终状态（所有边被删除）开始，逆序添加边，那么：

• 节点第一次通过新添加的边连接到节点1所在的连通分量时，就是该节点的"死亡时间"
• 因为一旦连接到节点1，在后续的GC操作中就不会被回收

存活时间计算

对于节点$i$：

• 如果始终未连接到节点1：存活到程序结束 $t_i = q + 1$
• 如果在时刻$T$首次连接到节点1：存活到下一次GC操作 $t_i = \text{next\_gc\_after}(T)$

算法框架

步骤1：预处理操作序列

• 记录每条边的删除时间
• 记录所有GC操作的发生时间
• 建立边的时间存活区间 $[0, \text{delete\_time} - 1]$

步骤2：逆向时间处理

从时刻$q$开始倒序遍历到时刻$1$：

当遇到DELETE操作时：

• 实际上在逆序中是在添加这条边
• 使用并查集合并两个连通分量
• 如果合并涉及节点1所在的连通分量，更新新加入节点的死亡时间

当遇到GC操作时：

• 在逆序中记录这个时间点，用于计算存活时间

步骤3：并查集优化

• 使用按秩合并和路径压缩的并查集
• 在合并时，如果其中一个连通分量包含节点1：
  • 将节点1的连通分量作为合并后的根
  • 为新加入的节点设置死亡时间为当前逆序时间

步骤4：死亡时间传播

在并查集合并时，需要处理死亡时间的传播：

• 如果连通分量A（不含节点1）合并到连通分量B（含节点1）
• 那么A中所有节点的死亡时间都设置为当前逆序时间
• 这可以通过在并查集中维护额外的信息实现

数据结构设计

并查集扩展

struct DSU {
    vector<int> parent, rank, death_time;
    // death_time[i] 表示节点i所在连通分量的死亡时间
    // 如果连通分量包含节点1，death_time为实际死亡时间
    // 否则为无穷大（表示还未确定）
}

时间处理

• 预处理GC操作的时间序列，便于快速找到下一个GC时间
• 对于每个节点，记录其首次连接到节点1的时间$T$
• 实际死亡时间 = 下一个GC操作时间（如果存在），否则为$q+1$

复杂度分析

时间复杂度

• 并查集操作：$O(m \cdot \alpha(n))$
• 操作序列处理：$O(q)$
• 总复杂度：$O((n + m + q) \cdot \alpha(n))$

空间复杂度

• 并查集：$O(n)$
• 边信息：$O(m)$
• 操作记录：$O(q)$
• 总空间：$O(n + m + q)$

特殊情况处理

初始状态

• 节点1的死亡时间初始化为$q+1$（程序结束时删除）
• 其他节点的死亡时间初始化为无穷大

边删除时间

• 如果某条边从未被删除，其存活区间为$[0, q]$
• 在逆序处理时，这些边在时刻0就存在

多次GC操作

• 节点可能在多个GC操作时间点被回收
• 但实际死亡时间由其首次连接到节点1的时间决定

实现细节

死亡时间计算

对于节点$i$，设其首次连接到节点1的时间为$T$：

• 找到第一个满足 $gc\_time \geq T$ 的GC操作时间
• 如果存在：$death\_time = gc\_time$
• 否则：$death\_time = q + 1$

答案计算

最终答案 = $\sum_{i=1}^n a_i \times death\_time_i$

总结

本题的核心在于逆向时间处理和并查集的巧妙应用。通过从最终状态开始逐步添加边，可以高效地确定每个节点首次连接到节点1的时间，从而计算出准确的存活时间。这种方法避免了正向处理时复杂的连通性维护，将问题转化为经典的并查集应用。