题目传送门
这种图论题目其实应该用图论的方法，也就是双连通分量，但本蒟蒻太菜了，不会，只好用动态树(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)\)