自动搬运

查看原文

来自洛谷，原作者为

	pigstd Hello, the cruel world.

搬运于2025-08-24 22:08:19，当前版本为作者最后更新于2020-09-15 13:02:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们先考虑暴力

很容易想到一个$O((m+n) \times q)$的算法：用链表存图，用二维数组记录删去的边，然后每次查询就暴力dfs

然后我们可以发现，虽然$m$很大，但是$q$很小，这意味着大多数边是永远不会被删除的，所以我们可以离线，先用并查集把所有永远不会被删掉的边缩成一个点，然后暴力就好了

设查询的次数为$k$，时间复杂度大概是$O(((q-k)+n) \times k)$，能跑过去

code：正解

总结：在遇到不会做的题目时候，可以观察数据范围的特殊性，然后暴力对症下药