题意：ByteotiaByteotia 城有 nn 个城镇，mm 条双向道路。每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。输出共 nn 行，每行输出一个整数。第 ii 行输出的整数表示把与节点 ii 关联的所有边去掉以后（不去掉节点 ii 本身），无向图有多少个有序点 (x,y)(x,y)，满足 xx 和 yy 不连通。

由题知，应该对点的类型分类处理。

如果点 ii 是割点，那么把与 ii 关联的边全部去掉过后，图会分成几个连通块。我们应该求出每个连通块的大小，两两相乘相加。如果 ii 有 tt 个子节点，那么会产生 t+2t+2 个连通块，分别为如下三种：

  1. ii 单独为一个连通块；
  2. 每个子节点及其子树各自构成一个连通块；
  3. 除以上所有点之外的点构成一个连通块。

我们设一个数组 size[i]size[i]，代表以 ii 为根的子树大小，那么通过组合计数，得到的答案为：

size[s1]×(n−size[s1])+⋅⋅⋅size[st]×(n−size[st])+(n−1)+(n−1−∑k=1tsize[sk])×(1+∑k=1tsize[sk]) size[s _1] \times (n-size[s _1])+···size[s_t] \times (n-size[s _t])+(n-1)+(n-1-\sum _{k=1} ^{t} size[s_k]) \times (1+\sum _ {k=1} ^{t} size[s _k])

如果点 ii 不是割点，那么去掉边后，只有 ii 与其他 n−1n-1 个点不连通，答案为 2×(n−1)2\times(n-1)(要求有序点对，所以双倍)

所以只用把割点求出来，一次求每个点的值即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int head[501010],cnt;
int Index,cut[101010];
int dfn[101010],low[101010];
long long size[101010],ans[101010];
struct node
{
	int next;
	int to;
}e[2010100];
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void tarjan(int u)
{
	dfn[u]=low[u]=++Index;
	size[u]=1;
	int sum=0,flag=0;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			size[u]+=size[v];
			if(low[v]>=dfn[u])
			{
				flag++;
				ans[u]+=(long long)size[v]*(n-size[v]);
				sum+=size[v];
				if(u!=1||flag>1)
					cut[u]=1;
			}
		}
		else
			low[u]=min(low[u],dfn[v]);
	}
	if(cut[u])
		ans[u]+=(long long)(n-sum-1)*(sum+1)+(n-1);
	else
		ans[u]=2*(n-1);
}
int main()
{
	scanf("%d%d",&n,&m);
	cnt=1;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	tarjan(1);
	for(int i=1;i<=n;i++)
		printf("%lld\n",ans[i]);
	return 0;
}