F. 非学术问题 详细题解

题目重述

给定一个 $n$ 个顶点 $m$ 条边的连通无向图（无重边、无自环）。你可以恰好删除一条边，目标是使得删除后图中存在路径的顶点对 $(u,v)$（$1 \le u < v \le n$）的数量尽可能少。输出这个最小值。

核心观察

• 原始图是连通的，因此所有 $n(n-1)/2$ 个顶点对都是可达的。

• 删除一条边后，图可能分裂成两个连通分量（如果删除的是桥）或仍然连通（如果删除的是非桥）。

• 如果删除的是非桥，图仍然连通，那么所有顶点对依然可达，数量不变，即 $n(n-1)/2$。

• 如果删除的是桥，图分裂成两个连通分量，大小分别为 $s$ 和 $n-s$。此时：

  • 分量内部的顶点对依然可达，数量为 $\binom{s}{2} + \binom{n-s}{2}$。
  • 跨分量的顶点对（一个在左，一个在右）变得不可达，因此总可达对数为 $\binom{s}{2} + \binom{n-s}{2}$。
  • 显然，为了最小化可达对数，我们希望删除一个桥，使得两个分量的大小尽可能均衡，因为 $\binom{s}{2} + \binom{n-s}{2}$ 在 $s$ 接近 $n/2$ 时最小？实际上这个函数是凸的，最小值在 $s=1$ 或 $s=n-1$ 时取到？我们计算一下：$$f(s) = \frac{s(s-1)}{2} + \frac{(n-s)(n-s-1)}{2} = \frac{s^2 - s + (n-s)^2 - (n-s)}{2} = \frac{2s^2 - 2ns + n^2 - n}{2}. $$这是一条开口向上的抛物线，对称轴为 $s = n/2$，在 $s=1$ 或 $s=n-1$ 时取得大值，在 $s$ 靠近 $n/2$ 时取得小值？等等，我们想要最小化 $f(s)$，即希望两个分量的大小尽可能相等，因为这样内部对数的和最小。例如 $n=10$，$s=5$ 时 $f=10+10=20$；$s=1$ 时 $f=0+36=36$；$s=2$ 时 $f=1+28=29$。所以确实最小化在 $s$ 接近 $n/2$ 时。因此，我们要找的桥应该使得删除后两个分量的大小尽可能平衡。

• 但注意：删除一条边后，图可能分成两个连通分量，但桥可能不止一个，我们需要考虑所有桥，并计算删除该桥后的分量大小，取最小的 $f(s)$ 值。另外，如果原图没有桥（即边双连通），则任何删除都不会分裂图，答案就是原图的对数 $n(n-1)/2$。

算法步骤

1. 读入 $n,m$ 和图的邻接表。
2. 使用 Tarjan 算法（DFS）求所有桥（关键边）。在 DFS 过程中，维护每个顶点的 DFS 序 dfn[u] 和低链接值 low[u]。当 $low[v] > dfn[u]$ 时，边 $(u,v)$ 是桥。
3. 在同一个 DFS 过程中，同时计算以 $u$ 为根的子树大小 sz[u]（包含 $u$ 及其所有后代）。对于桥 $(u,v)$（假设 $v$ 是 $u$ 的子节点），删除该桥后，一侧连通分量的大小就是 sz[v]，另一侧大小为 $n - sz[v]$。此时可达对数为：$$\binom{sz[v]}{2} + \binom{n - sz[v]}{2} = \frac{sz[v](sz[v]-1)}{2} + \frac{(n-sz[v])(n-sz[v]-1)}{2}. $$
4. 遍历所有桥，计算该值，并取最小值。
5. 如果没有任何桥（即 min_sz 保持为初始最大可能值），则答案就是 $\binom{n}{2}$。
6. 输出答案。

正确性证明

• 桥的必要性：只有删除桥才会使图分裂，从而减少可达对的数量。删除非桥后图仍连通，可达对数量不变，因此最优解一定在删除某个桥时取得。
• 分量大小的计算：在 DFS 树中，如果 $(u,v)$ 是桥且 $v$ 是 $u$ 的子节点，则 $v$ 的子树就是删除该桥后 $v$ 所在的分量（因为桥将子树与其余部分断开）。子树大小 sz[v] 即该分量的大小。另一分量大小为 $n - sz[v]$。
• 可达对数公式：分量内部所有顶点对都是可达的，跨分量不可达，因此总可达对数等于两个分量内部对数之和。
• 最小值取法：由于我们枚举了所有桥，并计算了对应的可达对数，取最小值即得最优解。

复杂度分析

• Tarjan 算法一次 DFS 遍历所有顶点和边，时间复杂度 $O(n+m)$。
• 所有测试用例的 $n$ 和 $m$ 总和均不超过 $2\times 10^5$，因此总复杂度 $O(\sum (n+m))$，完全可行。

边界情况

• 当 $n=2$ 且只有一条边时，该边是桥，删除后两个点各自独立，内部无对，跨分量不可达，结果为 $0$，正确。
• 当图为完全图或环等无桥图时，没有桥，答案即原图的总对数 $\binom{n}{2}$。
• 注意使用 long long 存储答案，因为 $n$ 可达 $10^5$，$\binom{n}{2}$ 约为 $5\times 10^9$，需用 64 位整数。

示例验证

以第四个样例（$n=6$）的图为例，Tarjan 找到桥 $(3,4)$ 使得一侧大小为 $3$（顶点 $4,5,6$），另一侧大小为 $3$（顶点 $1,2,3$），则答案 $3$ 选 $2$ 加上 $3$ 选 $2$ 等于 $3+3=6$，与输出一致。

总结

本题的关键是识别出只有删除桥才会减少可达对数量，并且可达对数由桥两侧分量大小决定。通过 Tarjan 算法找出所有桥并计算分割后的内部对数，取最小值即可。该方法高效且准确，适用于大规模图。