Description

Byteotia城市有n个 towns, m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。

Input

输入n和m。( n<=100000 ,m<=500000 )

Output

输出n个数,其中第i个整数表示把与节点i关联的所有边去掉之后(不去掉节点i本身),无向图中有多少个有序点对(x,y),满足x和y不连通。

Sample Input

5 5
1 2
2 3
1 3
3 4
4 5

Sample Output

8
8
16
14
8

限制与约定

时间限制:1s

空间限制:128MB

std:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#define LL long long
using namespace std;
const int maxn=1e5+;
const int maxm=5e5+;
inline int read()
{
int a=;bool b=;char x=getchar();
while(x<''||''<x){
if(x=='-')b=;
x=getchar();
}
while(''<=x&&x<=''){
a=(a<<)+(a<<)+x-'';
x=getchar();
}
return b?a:-a;
}
int first[maxn],next[maxm*],to[maxm*],edge_count;
inline void add(int x,int y){
edge_count++;
to[edge_count]=y;
next[edge_count]=first[x];
first[x]=edge_count;
}
int pre[maxn],low[maxn],root,Time;
LL ans[maxn],size[maxn];
int n,m;
void tarjan(int u){
pre[u]=low[u]=++Time;
size[u]=; int temp=;
long long cnt=n-;
for(int i=first[u];i;i=next[i]){
int v=to[i];
if(pre[v]){
low[u]=min(low[u],pre[v]);
}
else{
tarjan(v);
low[u]=min(low[u],low[v]);
size[u]+=size[v]; if(pre[u]<=low[v]){
temp++;
if(u!=root || temp>){
ans[u]+=size[v]*(n-size[v]-);
cnt-=size[v];
}
}
}
}
ans[u]+=cnt*(n-cnt-);
}
int main()
{
n=read();m=read();
const LL N=n+n-;
for(int i=,x,y;i<=m;i++){
x=read();y=read();
add(x,y);add(y,x);
}
for(int i=;i<=n;i++){
if(pre[i])continue;
root=i;
tarjan(i);
}
for(int i=;i<=n;i++){
printf("%lld\n",ans[i]+N);
}
return ;
}

奇葩问题汇总{

1.数据范围为>maxint,故要开long long

2.其中不影响结果的变量cnt如果开int也会影响结果,

因为每一步都要考虑强制转换的问题!!!特别要注意,否则会傻逼!!!

3.因为是双向点对,所以不用复杂的记录当前已经分理出多少点->res[u]

直接乘就行还会变快,!!!而且类似的求单向点对也可以求完双向再/2即可,

排列组合很重要!!!

}

05-11 13:20