你的思路方向其实是对的，但核心问题在于直接按原顺序处理时，无法高效统计当前与v连通的未删除邻接点数量——毕竟树的度数是静态的，但实际有效邻接点是动态变化的，遍历邻接表的话最坏情况会超时（比如星型结构的顶点，每次操作都要遍历O(n)个邻接点）。

针对n和q都达到5e5的规模，最优解法是离线处理+并查集（Union-Find），利用并查集擅长合并的特性，通过反转查询顺序来规避拆分操作的难题，具体步骤如下：

1. 预处理所有查询与顶点状态 #

首先，我们需要先遍历所有q次查询，记录每个顶点的最终状态（初始默认所有顶点存在，每遇到一次删除/恢复就翻转该顶点的状态），同时把每个查询的操作类型（删除/恢复）也记录下来。

2. 反转查询顺序 #

因为并查集不支持高效的拆分操作，但合并操作是O(α(n))的近乎常数时间。所以我们把查询顺序倒过来：

• 原查询的「删除顶点v」→ 反转后变成「恢复顶点v」
• 原查询的「恢复顶点v」→ 反转后变成「删除顶点v」

初始时，我们只保留最终状态为存在的顶点，此时连通分量数量就是这些顶点的总数。

3. 用并查集处理反转后的查询 #

遍历反转后的查询，逐个处理：

• 当处理「恢复顶点v」（对应原查询的删除）：
  1. 先把v加入当前存在的顶点集合，连通分量数量+1
  2. 遍历v的所有邻接点u，如果u当前是存在的，就将v和u进行合并。每成功合并一次，连通分量数量就减1（因为两个独立的连通分量被合并成一个）
• 当处理「删除顶点v」（对应原查询的恢复）：
  这个操作在反转逻辑里不需要实时处理——因为我们初始状态已经排除了最终要删除的顶点，所以这类操作其实是在还原初始状态，我们只需要记录结果即可。

4. 还原结果 #

把处理反转查询得到的结果数组再反转一次，就是原查询每次操作后的连通分量数量。

为什么这个方法高效？ #

每个边只会在两个顶点都存在的时候被处理一次（合并操作），总时间复杂度是O(nα(n) + q)，完全能应对5e5的规模。相比你之前的思路，避免了每次操作遍历邻接表的最坏情况，把时间复杂度从可能的O(nq)降到了线性级别的近似。

如果你一定要在线处理（即不提前知道所有查询），那可以考虑使用动态连通性数据结构（比如Link-Cut Tree），但实现难度大很多，离线+并查集是这个问题的最优实践方案。

内容的提问来源于stack exchange，提问作者rambo42