D. 网络攻防

题意：一张无向图，求至多删除 \(k\) 条边使得图不连通的方案数。\(k\in [1,2]\)。

首先考虑 \(k=1\)，答案即为无向图中的桥边。预计得分 \(15\) 分。

对于 \(m\le 2\times 10^3\) 的数据，我们可以枚举一条边删除，求剩余图中的桥边数量，最后加上桥边数量即可。预计得分 \(30\) 分。

考虑 \(k=2\) 时的正解。对于一张图的连通性，我们可以求出原图的生成树，这时有更多的性质来判断连通性，此时由于 \(k=2\)，分类讨论。

1. 两条都是非树边

   显然所有点都可以通过树边连通，没有方案。

2. 一条树边，一条非树边

   首先非树边一定不是桥边。

   两种情况：

   \(\bullet\) 若树边是桥边，那么非树边显然可以任选。

   \(\bullet\) 若树边不是桥边，一定存在至少 \(1\) 条跨过它的非树边（不然就是桥了），那么在生成树中实际上已经分为两个连通块，我们需要保证此时连通两个连通块的非树边不超过 \(2\) 条（即跨过该边的非树边），如果有，那么方案加一。（此时不管是判断小于 \(2\) 或等于 \(1\) 都能够得到答案）

3. 两条都是树边

   两种情况：

   \(\bullet\) 若至少有一条是桥边，总方案就是选树边的方案减去一条桥边都没选的方案。

   \(\bullet\) 若都不是桥边，此时是该题的瓶颈，我们需要一个结论：删除树边 \(a\)，\(b\) 后原图不连通的充要条件为

   覆盖了边 \(a\) 的非树边集 \(S_a\) 与覆盖了边 \(b\) 的非树边集 \(S_b\) 满足 \(S_a\) = \(S_b\)。

   简单来说就是删去两条边后，生成树上分为了三个连通块，画图可知，唯一不连通的方式即为两个连通块相连，剩下一个连通块孤立。

对于有桥边的方案都较为好求，我们考虑不是桥边的情况如何求解。

对于一条树边，一条非树边，我们需要求出跨过该树边的非树边数量，考虑枚举每条非树边 \((u,v)\)，此时生成树上 \(u\) 到 \(v\) 的路径上的边都被跨过了，可以利用树上差分的思想快速统计。

对于两条树边，我们需要知道每条边被哪些边跨过，暴力的做法容易实现，直接把 \(u\) 到 \(v\) 的路径都走一遍。这但是不好快速求的，利用 bitset 优化可以到 \(O(\frac{nm}{w})\)，预计得分 \(60\) 分。

我们考虑让每个方案都得到一个唯一的权值，考虑随机化。将每条非树边都附上一个 \([0,2^{64})\) 的随机权值，做树上路径异或，若两边的异或值相等，说明边集相等。类似生日悖论，证明可知，这样发生冲突的可能性是很小的。

\(\prod\limits_{i=1}^{n-2}(1-i\times 2^{-64})\ge (1−10^5\times 2^{−64})^{100000}\approx 0.99999999945789\)

用 unordered_map 统计答案，复杂度即为树上差分的复杂度 \(O(m\log n)\)。

总结：对于连通性，我们可以求桥边，还可以做生成树，此时树上的性质更多：桥边在树上，每个点有唯一路径，并且将边分为非树边和树边两种。由于 \(k\) 值非常小，我们可以考虑分类讨论，对于求统计相同方案的数量，可以考虑哈希随机化。