挺难的。。

---

这道题以点与点的结合作为问题，问我们如果一个点被删掉，那么有几组点的有序结合不能进行。

题目给的是无向图，所以内存双倍。

不知道为什么，与割点有关系。

如果一个点不是割点，那么去掉这一个点，其他点之间的相互到达显然都不会被影响，而只有被割的点与其他点之间的才受影响。

如果一个点是割点，那么事情就大了。被割掉的每一边中的点互相无法到达。

对于第一种情况，答案显然是\(2(n -1)\)。

第二种就难了。

听一听这种思路：

如何判断一个点是割点？就是dfn[u] <= low[v]。

那么如果跑tarjan的时候满足这个条件，那么是不是以v为根的dfs子树都会被割掉？

可以记录一个变量z，表示当前已经割掉的点的数目。

那么当我们新割了一些点，被割的点与新割的点就无法访问，我们就乘上去。同时更新z变量。

同病相怜的考虑完，还有一种情况：被割掉的点与不会被割掉的点之间无法相互访问。也乘上去。

显然那个\(2(n-1)\)是无论如何都会有的，我们加上去。

有时间再重新理解一下：

#include
    
     #include
     
      #include
      
       const int maxn = 100005, maxm = 500005;struct Edges{    int next, to;} e[maxm << 1];int head[maxn], tot;int dfn[maxn], low[maxn], dtot;long long ans[maxn];int size[maxn];int base;int n, m;bool cut[maxn];int read(){    int ans = 0, s = 1;    char ch = getchar();    while(ch > '9' || ch < '0')    {        if(ch == '-') s = -1;        ch = getchar();    }    while(ch >= '0' && ch <= '9')    {        ans = ans * 10 + ch - '0';        ch = getchar();    }    return s * ans;}void link(int u, int v){    e[++tot] = (Edges){head[u], v};    head[u] = tot;}void tarjan(int u, int root){    dfn[u] = low[u] = ++dtot;    size[u] = 1;    int child = 0;    long long z = 0;//已经被割掉的点的数量    for(int i = head[u]; i; i = e[i].next)    {        int v = e[i].to;        if(!dfn[v])        {            tarjan(v, root);            size[u] += size[v];            low[u] = std::min(low[u], low[v]);            if(dfn[u] <= low[v])//被割掉的子树            {                ans[u] += z * size[v];//已经被割的跟现在被割的无法相互到达                z += size[v];//update            }        }        low[u] = std::min(low[u], dfn[v]);    }    ans[u] += z * (n - z - 1);//割掉的点与未割掉的点无法相互到达}int main(){    n = read(), m = read();    while(m--)    {        int u = read(), v = read();        link(u, v); link(v, u);    }    for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, i);    for(int i = 1; i <= n; i++)    {        printf("%lld\n", (ans[i] + n - 1) << 1);    }    return 0;}