原址：https://jzoj.net/senior/#main/show/3896

3896. 【NOIP2014模拟10.26】战争游戏 (Standard IO)

Description

InputOutput# Sample Input

7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7

Sample Output

18
6
6
6
6
6
6

Data Constraint

比赛时所有人除了满分就WA 0 我是WA 0

正解Tarjan算法，求割点。

什么是必经点？a-b如果不经过T，a-b相当于隔绝状态。（T是a-b必经点）

也就是说，去掉T后此图会分裂，a，b处于不同的连通块内。

这TM 不就是割点吗？

想到这点，此题so easy

红色为割点（它上面那个点也是，此处拿它举例子，绿色是1连通块的点，蓝色是2连通块的点，粉色是3连通块的点，橙色是4连通块的点

拿2连通块举例，它与非2联通块的点连接，红点（割点）都是一个必经点。为了方便计算，像（2~3）3是必经点这种必经点在起点终点上的我们最后再计算

那么目前要计算的点只剩下绿紫橙点了，观察它们两两间路径割点都是必经点。

用乘法原理，用2联通块点数*（总点数-1-2联通块点数）即可得出2联通块与别的点经过割点的次数。（-1减的是割点）

3，4联通块同理。

一个巨大的问题：1联通块呢？

2，3，4联通块是红点的子节点（直接和间接），可以在Tarjan递归时顺便处理

但是对于割点的祖先，我们必须在Tarjan枚举儿子完后再加答案

加答案也很简单，用割点的儿子总数*（总点数-1-割点的儿子总数）即可（-1减的还是割点）

注意：加答案加给割点，非割点Tarjan中没有答案；观察发现答案会重复（每个x~y都会在x的联通块中算一次，在y的联通块中再算一次，所以答案要除2）

还有个事，如果此点不是割点，它就没答案了?

当然不可能！注意，割点在必经点中只算中间点，依题意，2~3路径中2,3也算必经点 又因为（A，B）跟（B，A）只算一对，每个点 答案都要加n-1，算上必经点在起点，终点的情况。

此题解决了！

代码

(仅供参考，请勿抄袭）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int i,j,k,m,n,o,p,l,s,t,x,y,sum;
int dfn[100001],low[100001],ans[100001],num[100001];
int f[400001][3],q[400001];
void insert(int x,int y)
{ f[++t][1]=y,f[t][2]=q[x],q[x]=t; }
void Tarjan(int x)
{
	dfn[x]=low[x]=++sum;num[x]=1;
	int tot=0;
	for (int k=q[x];k;k=f[k][2])
	{
		int y=f[k][1];
		if (!dfn[y]) {
			Tarjan(y);
			low[x]=min(low[x],low[y]);
			if (dfn[x]<=low[y])
			{
				ans[x]+=num[y]*(n-1-num[y]);
				tot+=num[y];
			}
			num[x]+=num[y];
		} else low[x]=min(low[x],dfn[y]);
	}
	ans[x]+=tot*(n-1-tot);
}
int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		insert(x,y),insert(y,x);
	}	
	Tarjan(1);
	for (i=1;i<=n;i++) printf("%d\n",ans[i]/2+n-1);
	return 0;
}