Problem
给定一个有n个点m条边的无向连通图，可以删掉两条边，问有多少种方案使得这个连通图不连通
1≤n≤105,1≤m≤3×105
Solution
随机大法走天下啊。。。
考虑图的dfs树，对于非树边，我们随机一个(0,2^64)的权值，然后对于一条树边，其权值为覆盖它的非树边的xor和，那么对于一个边集，如果我们可以割掉这个边集使得图不连通，那么其必有一个子集的xor和为0。题目要求删掉两条，就是说两条的权值相同，或其中一条为0，于是可以直接按照边权排序，直接计算即可。
由于我们是随机的，这使得出错的概率变得很小很小可以省略。
cc真的有鬼，我交了两个一样的代码一个对了一个错了。。。
Code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;int get(){char ch;int s=0;bool bz=0;while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');if (ch=='-')bz=1;else s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';if (bz)return -s;return s;
}typedef long long LL;const int N = 1e+5+10;
const int M = 3e+5+10;struct edge{int x,id,nxt;
}e[M*2];
bool bz[M],vis[N];
int h[N],tot,d[N],n,m,dep[N];
LL v[M];void inse(int x,int y,int id){e[++tot].x=y;e[tot].id=id;e[tot].nxt=h[x];h[x]=tot;
}void dfs(int x){vis[x]=1;for(int p=h[x];p;p=e[p].nxt)if (e[p].id!=d[x]){if (!vis[e[p].x]){d[e[p].x]=e[p].id;dep[e[p].x]=dep[x]+1;dfs(e[p].x);v[d[x]]^=v[d[e[p].x]];}elseif (!bz[e[p].id]){bz[e[p].id]=1;v[e[p].id]=0;fo(i,1,21)v[e[p].id]=v[e[p].id]*8+rand()%8;v[d[x]]^=v[e[p].id];}else v[d[x]]^=v[e[p].id];}if (!d[x])v[0]=0;
}int main(){srand(16789);n=get();m=get();fo(i,1,m){int x=get(),y=get();inse(x,y,i);inse(y,x,i);}dfs(1);sort(v+1,v+1+m);int w=m;fo(i,1,m)if (v[i]!=0){w=i-1;break;}LL ans=0;ans=LL(w)*(m-w)+LL(w)*(w-1)/2;int s=0;fo(i,w+1,m){if (v[i]!=v[i-1]){ans=ans+LL(s)*(s-1)/2;s=0;}s++;}ans=ans+LL(s)*(s-1)/2;printf("%lld\n",ans);return 0;
}