题目描述
在 P 市的交通规划中，有一个复杂而精妙的交通网络。这个庞大的网络涵盖了 \(n\) 个交通枢纽，它们通过 \(m\) 条纵横交错的道路（均为双向道路）相互紧密连接，形成了一个高效运转的整体。
在这个网络中，枢纽 \(a\) 和 \(b\) 扮演着极为特殊且关键的角色，它们是城市交通的重要物资中转站，承载着大量物资的调配和运输任务，对整个城市的物资流通起着举足轻重的作用。
现在，为了探究枢纽 \(a,b\) 的运输压力以便后续的城市规划，研究员希望探究其他枢纽在物流运输过程中经过 \(a,b\) 的情况。也就是在不直接涉及这两个特殊枢纽作为起始点或终点的情况下，研究员试图探究有多少对其他交通枢纽之间的通行路径必然会经过这两个重要的物资中转站。
具体来说，要找出满足以下严格条件的二元组 \((u,v)\) 的数量：
- \(1 \le u < v \le n\)；
- \(u \not= a, v \not= a, u \not= b, v \not= b\)；
- 任意一条从 \(u\) 到 \(v\) 的路径都经过 \(a,b\)。
请你协助研究员完成这一次调查。
输入格式
输入第一行包含四个整数 \(n,m,a,b\)，分别表示枢纽数量，道路数量，以及两个重要枢纽的编号。
接下来 \(m\) 行，每行两个整数 \(u,v\)，描述了一条双向道路 \((u,v)\)。
保证从任何枢纽，你都可以通过双向道路到达任何其他枢纽，一对枢纽之间可能有不止一条路。
输出格式
输出共一行，表示满足上述要求的 \((u,v)\) 对数。
样例 1 输入
7 7 3 5
1 2
2 3
3 4
4 5
5 6
6 7
7 5
样例 1 输出
4
样例 1 解释
合法的枢纽对有：\((1,6),(1,7),(2,6),(2,7)\)。
样例 2 输入
4 5 2 3
1 2
2 3
3 4
4 1
4 2
样例 2 输出
0
其余样例见下发文件。
数据规模与约定
- 对于 \(20\%\) 的数据，保证 \(n \le 10, m \le 15\)。
- 对于 \(40\%\) 的数据，保证 \(n \le 50,m \le 200\)。
- 对于另 \(20\%\) 的数据，保证 \(m = n - 1\)。
- 对于 \(100\%\) 的数据，保证 \(4 \le n \le 2 \times 10^5,n-1 \le m \le 5 \times 10^5,a \not=b\)。
分析
通过分析题目，不难发现，对于一对必需经过 \(a,b\) 的二元组，若将原图以 \(a,b\) 为分界点隔开，则 \(a,b\) 必须处在不同的联通块内且不在 \(a-b\) 路径上。二元组对数等于这两个连通块大小的乘积，\(dfs\) 即可。
连通块大小计算(重点)
想知道任意一侧连通块的大小只需将一个关键点设为起点，搜索直到到达另一个节点，用总节点个数减去搜索过程中所经过的节点个数即为此侧连通块大小
不开 longlong ( )( )( )
Code
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 3e5+5;
int n,m,a,b;struct Edge {int to,next;
} edge[2*N];
int idx=0,head[N*2];
inline void add(int from,int to) {edge[++idx].to=to;edge[idx].next=head[from];head[from]=idx;return;
}bool vis[N];
void dfs(int x,int fa,int end) {vis[x]=true;if(x==end) return;for(int i=head[x];i;i=edge[i].next) {int to = edge[i].to;if(vis[to]) continue;dfs(to,x,end);}
}long long A=0,B=0;
int main() {// freopen("in.in","r",stdin);cin>>n>>m>>a>>b;for(int i=1;i<=m;i++) {int u,v; cin>>u>>v;add(u,v);add(v,u);}int tmp=0;dfs(a,0,b);for(int i=1;i<=n;i++) if(vis[i]==true) tmp++;B=n-tmp; tmp=0;memset(vis,0,sizeof vis);dfs(b,0,a);for(int i=1;i<=n;i++) if(vis[i]==true) tmp++;A=n-tmp;cout<<A*B<<endl;return 0;
}