好文收藏夹

题目大意 给出一张无向图以及两个点 a,b ，之后您需要求出有多少对点对 (u,v) 满足从 u 到 v 的任意一条路径都必须同时经过点 a,b 。 同时若 (u,v) 中的任何一个点为 a 或 b ，则这个点对也不合法。 n <= 1e5 吐槽 虽然确实挺有意思，但是这么简单的题，出到 Div2E 我觉得有点不合适吧QAQ。 另外这一篇题解中您可能会大量看见某些词的重复使用。 题解 我们从 a 点开始bfs，对所有到达的点染色一次，同时要求此时不能经过 b 。 之后从 b 点开始bfs，对所有到达的点染色一次，同时要求此时不能经过 a 。 此时我们应当有三类点：只被 a 染色、只被 b 染色、同时被 a,b 染色，由于图是联通的，所以不会存在没有被染色的点。 答案是第一类点的数量乘上第二类点的数量。 证明 我们考虑一对合法的点 (u,v) ，为方便起见我们假设 u 是第一类点而 v 是第二类点。 之后我们思考一下 u 只被 a 染色的意义是什么。 实际上这意味着 u 可以通过某些方式到达 a ，但它不能通过 a 以外的任何点到达 b ，换句话而言若 u 想有一条到 b 的路径，那么其路径上必须经过 a 。 实际上 v 只被 b 染色的意义是相似的。 之后我们想证明什么？ 我们想证明任何一条从 u 到 v 的路径都必须经过 a,b 。 我们讨论一下一条从 u 到 v 的路径的情况。 实际上我们只需要考虑一下是否可以存在不同时经过 a,b 的路径的可能性就好了。 具体来说，我们假设存在一条路径使得其不经过 b ，那么应当有： 从 v 能不经过 b 到达 u 。 u 能不经过 b 到达 a 。 从 v 能不经过 b 到达 a 于是我们发现此时出现了矛盾，第二类点实际上是不能通过 b 以外的点到达 a 的，于是不可能存在这样一条路径。 证明不存在一条路径使其不经过 a 也可以用相同的方法证明出来。 于是我们就证明了至少有这么多点对是可行的。 之后我们还需要证明其他的点对是不可行的。。 实际上这里的证明和上面的证明也是相似的所以略过。 然后就把这个做法的正确性证明出来了~ 代码 #include   ...