删边（cip）
给出一个没有重边和自环的无向图，现在要求删除其中两条边，使得图仍然保持连通。
你的任务是计算有多少组不合法的选边方案。注意方案是无序二元组。
Sol
神题，无从下手啊。
考虑点dfs建出dfs树，边分为两种--树边，非树边。
那么割断两条非树边显然不行。
考虑割一条树边a和一条非树边b，当b为a子树内唯一返祖边或a子树无返祖边时不行。
考虑两条树边ab，我们把一条返祖边打在它覆盖的所有树边上，如果这两条非树边被覆盖的集合相同，那么他们中间的那一段就会断开，就可以。
于是可以把每条返祖边给个hash值，开始处加，结束处减，统计每条边的覆盖集合，在排序统计下就行。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 300005
#define rand() ((rand()<<15)|rand())
#define ll unsigned long long
using namespace std;
int n,m,head[maxn],tot,flag[maxn],t;
int sum[maxn],sz[maxn],a[maxn],deep[maxn];
struct node{
int v,nex;int h;
}e[maxn*];
ll ans,ha[maxn];
void add(int t1,int t2){
e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;
}
void dfs(int k,int fa){
flag[k]=; deep[k]=deep[fa]+;
for(int i=head[k];i;i=e[i].nex){
if(flag[e[i].v]){
if(e[i].v!=fa&&deep[e[i].v]<deep[k]){
ha[e[i].v]-=e[i].h;
ha[k]+=e[i].h;
sz[k]++;sz[e[i].v]--;
}
continue;
}
dfs(e[i].v,k);
}
}
void tj(int k){
flag[k]=;
for(int i=head[k];i;i=e[i].nex){
if(flag[e[i].v])continue;
tj(e[i].v);
sz[k]+=sz[e[i].v];
ha[k]+=ha[e[i].v];
}
if(k!=){
if(!sz[k])ans+=m-,t++;
if(sz[k]==)ans++;
}
}
int main(){
srand();
cin>>n>>m;
for(int i=,t1,t2;i<=m;i++){
scanf("%d%d",&t1,&t2);
add(t1,t2);add(t2,t1);
e[tot].h=e[tot-].h=rand()*rand();
}
dfs(,);
memset(flag,,sizeof flag);tj();
sort(ha+,ha+n+);
for(int i=;i<=n;i++){
int j=i;
for(;ha[j+]==ha[i];j++);
if(ha[j]==)continue;
int len=j-i+;
ans=ans+1LL*len*(len-)/;
i=j;
}
ans=ans-1LL*t*(t-)/;
cout<<ans<<endl;
return ;
}