记录编号	208699	评测结果	AAAWAAAAAW
题目名称	[Ural 1557]网络攻击（重题）	最终得分	80
用户昵称	cstdio	是否通过	未通过
代码语言	C++	运行时间	0.107 s
提交时间	2015-11-18 10:31:27	内存使用	6.04 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int SIZEN=100010,SIZEM=300010;
int N,M;
int U[SIZEM],V[SIZEM];
int fa[SIZEN],dfslis[SIZEN];
int tot=0;
vector<int> c[SIZEN];
int dep[SIZEN]={0};
int to(int x,int i){
	return x==U[i]?V[i]:U[i];
}
LL llrandom(void){
	LL ans=0;
	for(int i=0;i<4;i++){
		ans<<=16;
		ans|=rand();
	}
	return ans;
}
int cov[SIZEN];
LL val[SIZEN];
void work(void){
	for(int i=1;i<=M;i++){
		if(dep[U[i]]<dep[V[i]]) swap(U[i],V[i]);
		cov[U[i]]++,cov[V[i]]--;
		if(dep[V[i]]+1!=dep[U[i]]){
			LL v=llrandom();
			val[U[i]]^=v,val[V[i]]^=v;
		}
	}
	for(int i=N;i>=1;i--){
		cov[fa[dfslis[i]]]+=cov[dfslis[i]];
		val[fa[dfslis[i]]]^=val[dfslis[i]];
	}
	LL ans=count(cov+1,cov+1+N,2);//只被一条回边覆盖的树边数量
	LL bridge=count(cov+1,cov+1+N,1);//不被回边覆盖的树边,即桥边数量
	ans+=bridge*(bridge-1)/2+bridge*(M-bridge);//桥和随便一条边
	sort(val+1,val+1+N);
	int len=0;
	for(int i=1;i<=N;i++){
		if(!val[i]) continue;//未被覆盖
		if(val[i]==val[i-1]) ans+=len++;//这条树边,和前面某条hash相同的树边
		else len=1; 
	}
	printf("%lld\n",ans);
}
void DFS(int x){
	dfslis[++tot]=x;
	for(int i=0;i<c[x].size();i++){
		int u=to(x,c[x][i]);
		if(!dep[u]){
			fa[u]=x;
			dep[u]=dep[x]+1;
			DFS(u);
		}
	}
}
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++){
		scanf("%d%d",&U[i],&V[i]);
		c[U[i]].push_back(i);
		c[V[i]].push_back(i);
	}
}
int main(){
	freopen("Attack.in","r",stdin);
	freopen("Attack.out","w",stdout);
	read();
	dep[1]=1;
	DFS(1);
	work();
	return 0;
}