There are 𝑛 cities in Berland and some pairs of them are connected by two-way roads. It is guaranteed that you can pass from any city to any other, moving along the roads. Cities are numerated from 1 to 𝑛.

Two fairs are currently taking place in Berland — they are held in two different cities 𝑎 and 𝑏 (1≤𝑎,𝑏≤𝑛; 𝑎≠𝑏).

Find the number of pairs of cities 𝑥 and 𝑦 (𝑥≠𝑎,𝑥≠𝑏,𝑦≠𝑎,𝑦≠𝑏) such that if you go from 𝑥 to 𝑦 you will have to go through both fairs (the order of visits doesn't matter). Formally, you need to find the number of pairs of cities 𝑥,𝑦 such that any path from 𝑥 to 𝑦 goes through 𝑎 and 𝑏 (in any order).

Print the required number of pairs. The order of two cities in a pair does not matter, that is, the pairs (𝑥,𝑦) and (𝑦,𝑥) must be taken into account only once.

链接🔗

「CodeForces 1007B」Pave the Parallelepiped

题解

直接说结论吧
visavisa表示不经过点bb是否能到达点aa
visbvisb表示不经过点aa是否能到达点bb
如果visa[i] && !visb[i] 说明该点被a支配
如果visb[i] && !visa[i] 说明该点被b支配

答案就是上面两个的乘积

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxd = 2e5+10;
int main()
{
//     freopen("a.in","r",stdin);
//     freopen("k.out","w",stdout);
    int t;scanf("%d",&t);
    while(t--)
    {
        int n,m,a,b;
        scanf("%d %d %d %d",&n,&m,&a,&b);
        vector<int> G[n+1];
        for(int i=1;i<=m;i++)
        {
            int x,y;scanf("%d %d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        int visa[n+1],visb[n+1];
        for(int i=1;i<=n;i++) visa[i] = visb[i] = 0;
        queue<int> que;
        que.push(a);
        visa[a] = visa[b] = 1;
        while(!que.empty())
        {
            int x = que.front(); que.pop();
            for(auto v: G[x])
                if(v!= b && !visa[v]) visa[v] = 1,que.push(v);
        }

        que.push(b);
        visb[a] = visb[b] = 1;
        while(!que.empty())
        {
            int x = que.front(); que.pop();
            for(auto v: G[x])
                if(v!= a && !visb[v]) visb[v] = 1,que.push(v);
        }

        long long aa = 0ll;
        long long bb = 0ll;
        for(int i=1;i<=n;i++)
        {
            if(visa[i] && !visb[i]) aa++;
            if(visb[i] && !visa[i]) bb++;
        }
        printf("%lld\n",aa*bb);
    }
    return 0;
}