读题可以发现，如果两个村庄不能互相连通，那就算作一对 （a<b）。
显然是可以用floyd全局多源最短路来做的，如果不存在最短路，那么就是不能互通，但是这道题的数据范围N<=10^5，跑floyd复杂度为O（n^3）即10^15远大于10^8，显然是不行，复杂度级别只能是O（n），线性的，或者O（nlogn）。
看一下样例说明
显然如果两个村庄位于同一个连通块中，必然找不出（a<b），如果不在同一个连通块中，必然会产生（a<b），且数量刚好是第一个连通块的村庄数量 乘以 第二个连通块的数量。
为什么？
假设下图，1和2相连，3和4相连。
明显可以发现1与3,4，都不相连，产生了第二个连通块村庄数量的（a<b）
2与3,4，也不相连，即为2*2=4。
所以直接使用并查集：【模板】并查集 - 洛谷
初始给每个村庄都分配一个连通块，如果有桥相连，就把它们加入同一个连通块。
因为会摧毁编号为1~k的桥，所以输入的时候只需要i>k的部分，不需要合并被摧毁的部分。
细节（以样例说明）：第四座桥把4接到了连通块1上，第五座桥把1接到了连通块3上，这里就出现了一个问题，4并没有被更新，所以最后还要再跑一遍find，更新所有情况。（本蒟蒻考试的时候熬夜昏迷了，没想到这一点）
应该能AC的代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,u,v,f[100001],cnt,ans;
bitset<100001>vis;
int a[100001];//连通块编号,其中村庄数量
vector<int>a_;
//定义f[i]=j为：i村庄在连通块j中
int find(int x){
if(f[x]==x)return x;
else return f[x]= find(f[x]);
}
void unit(int x,int y){
x= find(x),y= find(y);
f[x]=y;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>k;
for(int i=1;i<=n;++i)//初始化每个村庄的连通块
f[i]=i;
for(int i=1;i<=m;++i){
cin>>u>>v;
if(i>k){//1~k的桥全部被摧毁,只需要i>k的桥
unit(u,v);
}
}
for(int i=1;i<=n;++i)//跑一遍find,更新最终情况
find(i);
for(int i=1;i<=n;++i){//累计连通块编号
a[f[i]]++;
}
for(int i=1;i<=n;++i)//把累计完的连通块全部拿出来
if(a[i])a_.push_back(a[i]);
for(int i=0;i<a_.size();++i)//配对连通块,累计答案
for(int j=i+1;j<a_.size();++j)
ans+=a_[i]*a_[j];
cout<<ans;
return 0;
}如果有错误或者有更好的思路，欢迎评论！
看看算法大赛还会不会开放OJ让我们再次测试。
同时预祝各位在2023/4/8的蓝桥杯省赛中while(true)rp++
别熬夜 : )