题意

传送门 Codeforces 1277E Two Fairs

题解

求无向图中不包含 a , b a,b a,b 的无序点对数量，这些点对 ( u , v ) (u,v) (u,v) 满足 u u u 与 v v v 间的任意路径都经过 a , b a,b a,b。

若点对 ( u , v ) (u,v) (u,v) 满足 u u u 与 v v v 间的任意路径都经过 a a a，则将 a a a 和以其为端点的连边删除后， u , v u,v u,v 属于不同的连通分量。设满足这样的点对集合为 A A A，对于 b b b 而言这样的集合为 B B B。根据容斥原理
A ∩ B = A + B − A ∪ B A\cap B=A+B-A\cup B A∩B=A+B−A∪B 其中 A ∩ B A\cap B A∩B 为所求。对于 A , B , A ∪ B A,B,A\cup B A,B,A∪B 都容易通过计算补集得到。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l, _ = r; i < _; ++i)
#define pb push_back
typedef long long ll;
const int MAXN = 2E5 + 5;
int T, N, M, A, B;
vector<int> G[MAXN];
int cc[2][MAXN];

void dfs(int id, int u, int k, int ban)
{
    if (u == ban)
        return;
    cc[id][u] = k;
    for (auto &v : G[u])
        if (cc[id][v] == -1)
            dfs(id, v, k, ban);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> N >> M >> A >> B;
        --A, --B;
        rep(i, 0, N) G[i].clear();
        rep(i, 0, M)
        {
            int u, v;
            cin >> u >> v;
            --u, --v;
            G[v].pb(u), G[u].pb(v);
        }
        rep(i, 0, 2) rep(u, 0, N) cc[i][u] = -1;
        int k = 0;
        rep(i, 0, N) if (cc[0][i] == -1) dfs(0, i, k++, A);
        k = 0;
        rep(i, 0, N) if (cc[1][i] == -1) dfs(1, i, k++, B);

        map<int, int> cnt[2];
        rep(i, 0, 2) rep(u, 0, N) if (u != A && u != B)++ cnt[i][cc[i][u]];
        int rst = N - 2;
        ll res = (ll)rst * (rst - 1);
        rep(i, 0, 2) for (auto &p : cnt[i]) res -= (ll)p.second * (p.second - 1) / 2;

        map<pair<int, int>, int> pcnt;
        rep(i, 0, N) if (i != A && i != B)++ pcnt[{cc[0][i], cc[1][i]}];
        ll t = (ll)rst * (rst - 1) / 2;
        for (auto &p : pcnt)
            t -= (ll)p.second * (p.second - 1) / 2;
        cout << res - t << '\n';
    }
    return 0;
}