1526：Blockade

题目描述

原题来自：POI 2008

Byteotia 城市有 $n$ 个城镇，$m$ 条双向道路。每条道路连接两个不同的城镇，没有重复的道路，所有城镇连通。

输出 $n$ 个数，代表如果把第 $i$ 个点去掉，将有多少对点不能互通。

输入格式

输入 $n, m$ 及 $m$ 条边。

输出格式

输出 $n$ 个数，代表如果把第 $i$ 个点去掉，将有多少对点不能互通。

样例

样例输入 #1

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

样例输出 #1

8
8
16
14
8

样例解释 #1

• $n=5$ 个城镇，$m=5$ 条边。
• 边：
  1. $1-2$
  2. $2-3$
  3. $1-3$
  4. $3-4$
  5. $4-5$
• 原图是连通的。
• 删除每个点后，计算不能互相到达的点对数量（有序对还是无序对？根据样例输出数值推断是无序对，因为总数是 $n(n-1)/2$，删除点后计算不能互通的点对）。
• 删除点 $1$：
  • 剩余点 $\{2,3,4,5\}$，但图可能不连通。实际上删除 $1$ 后，$2$ 和 $3$ 仍然连通（直接相连），$3,4,5$ 连通，所以所有点仍然连通？不对，$2$ 和 $3$ 连通，$3$ 和 $4$ 连通，所以全部连通。但样例输出是 $8$，说明不连通？可能我理解有误。
• 根据样例输出，删除点 $3$ 时答案最大（$16$），因为 $3$ 是割点，删除后图分裂为几个连通块。
• 具体计算需要用到割点及点双连通分量的知识。

注意：点对是无序的，即 $(u,v)$ 和 $(v,u)$ 算同一对。

数据范围

• $n \le 10^5$
• $m \le 5 \times 10^5$

时空限制

• 时间限制：1000 ms
• 内存限制：165888 KB

注意：本题需要计算删除每个点后，图中不能互相到达的点对数量。对于非割点，删除后图仍然连通（除了该点本身被移除），所以不能互通的点对数为 $n-1$（即该点与其他所有点构成的点对）。对于割点，删除后图会分裂成若干个连通块，不能互通的点对数为：所有连通块两两之间的点对数量之和。具体地，设删除割点后，产生 $k$ 个连通块，大小分别为 $size_1, size_2, \dots, size_k$，则不能互通的点对数为：

$$\sum_{i=1}^k \sum_{j=i+1}^k size_i \cdot size_j = \frac{1}{2} \left( \left( \sum_{i=1}^k size_i \right)^2 - \sum_{i=1}^k size_i^2 \right)$$

注意，这里不考虑被删除的点本身（因为它已经不在了），但原图中与它相连的点对也算不能互通？实际上，删除点 $u$ 后，所有原本通过 $u$ 连通的点对可能变得不连通，我们需要计算所有点对 $(x,y)$（$x \ne u, y \ne u$）中不能连通的数量。可以通过 Tarjan 算法求割点时，计算每个子树的节点数。对于根节点（割点），其子树的节点数就是 $size_i$，另外还有一个连通块是除该子树外的其他部分（包括其他子树和祖先部分）。对于非根割点，类似处理。注意答案要用 long long 存储。