P2542 [AHOI2005] 航线规划の题解

题目传送门

这种图论题目其实应该用图论的方法，也就是双连通分量，但本蒟蒻太菜了，不会，只好用动态树(LCT)水过去了

题目描述

有一个无向图，初始时给定 \(n\) 个顶点和 \(m\) 条边的连接情况。随后依次执行 \(Q\) 个操作，操作分为两种：

破坏操作 (C 类型)：断开一条指定的边（保证该边当前存在）。

查询操作 (Q 类型)：询问两个顶点 \(u\) 和 \(v\) 之间关键路径的数量。关键路径指的是：如果一条边被删除，会导致 \(u\) 和 \(v\) 不再连通，那么这条边就是 \(u\) 和 \(v\) 之间的关键路径。

我们的任务是处理所有查询操作，并输出每个查询的答案。

数据范围
\(n \leq 3\times 10^4\)

\(m \leq 10^5\)

\(Q \leq 4\times 10^4\)

初始时图是连通的（重要性质）

解题方法

关键思路：离线处理 + 动态树（LCT）

1. 问题转化

首先理解"关键路径"的本质：在无向连通图中，两个顶点 \(u\) 和 \(v\) 之间的关键路径实际上就是 \(u\) 到 \(v\) 的路径上的桥（割边）。

桥的定义：如果删除一条边会使图的连通分量数量增加，那么这条边就是桥。

对于两个顶点 \(u\) 和 \(v\)，它们之间路径上的桥的数量就是答案。

2. 离线逆向处理

由于题目支持动态删边操作，直接处理较为困难。我们可以采用离线处理的逆向思维：

读入所有操作

从最终状态开始反向处理操作

把删除操作变为添加操作

为什么这样可以简化问题？

添加边比删除边更容易处理

添加一条边可能会使一些桥变成非桥（形成环）

从最终状态（边最少）开始，逐步恢复到初始状态

3. 使用动态树（LCT）维护桥

Link-Cut Tree (LCT) 是一种用于维护动态树的数据结构，支持：

link(x, y)：连接两个节点

cut(x, y)：断开两个节点

查询路径信息

对于本题，我们可以使用 LCT 来维护生成森林，并标记哪些边是桥。

核心思想：

初始时（最终状态），我们只知道那些从未被删除的边

反向处理时，当添加一条边 (u, v)：

如果 u 和 v 不连通，则直接连接，这条边是桥

如果 u 和 v 已经连通，则添加这条边会形成一个环，环上的所有边都不再是桥

4. 具体实现步骤

读入与预处理：

读入所有边和操作

标记每条边是否被删除

确定最终状态的边集

建立初始生成森林：

使用最终状态的边建立生成森林

每条边都是桥（因为是最小连通）

反向处理操作：

对于查询操作：计算路径上的桥的数量

对于添加边操作：

如果不连通，直接连接（标记为桥）

如果连通，找到路径，将路径上所有边标记为非桥

输出答案：

按照正向顺序输出查询结果

复杂度分析

预处理：\(O(m \log n)\)

LCT 操作：每次 \(O(\log n)\)

总复杂度：\(O((m+Q) \log n)\)

空间复杂度：\(O(n+m+Q)\)