题目

割点模板题。

可以将图中的所有点分成两部分，一部分是去掉之后不影响图的连通性的点，一部分是去掉之后影响连通性的点，称其为割点。

然后分两种情况讨论，如果该点不是割点，则最终结果直接加上2*(n-1)。如果是的话，就求子树的每块连通块大小。

一个点的子树可以分成两类：存在返祖边或不存在。

对于前者，割掉该点并不影响连通性，所以和祖先算作一个联通块；

对于后者，割掉该点将使得其变为独立的联通块，所以在搜索时顺便计算\(size\)。

于是可以方便地算出后者的\(size\)之和sum，而前者总大小即为\(n-sum-1\)。

在搜索时一边累加\(sum\)，一边累加答案，最后加上\(n-1\)，得到的是无序点对的个数。

然后乘法原理即可。

#include <iostream>

#include <stdio.h>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cmath>

#define int long long

using namespace std;

struct edg {

    int to, len, nex;

}e[1000100];

int lin[300100], dfn[300100], low[300100], siz[301000], cut[300100], tot, cnt, n, m;

vector <int> s[300010];

inline void add(int f, int t)

{

    e[++cnt].to = t;

    e[cnt].nex = lin[f];

    lin[f] = cnt;

}

void Tarjan(int fa, int u)

{

    dfn[u] = low[u] = ++tot;	int temp;

    siz[u]++;

    temp = 1;

    for (int i = lin[u]; i; i = e[i].nex)

    {

        int to = e[i].to; if (to == fa) continue;

        if (!dfn[to])

        {

            Tarjan(u, to);

            siz[u] += siz[to];

            low[u] = min(low[u], low[to]);

            if (low[to] >= dfn[u])

            {

                temp += siz[to];

                s[u].push_back(siz[to]);

                cut[u] = 1;

            }

        }

        else low[u] = min(low[u], low[to]);

    }//求割点

        s[u].push_back (n - temp);

}

signed main()

{

    scanf("%lld%lld", &n, &m);

 	for (int i = 1; i <= n; i++)

        s[i].reserve(5);

    for (int i = 1; i <= m; i++)

    {

        int a, b;

        scanf("%lld%lld", &a, &b);

        add(a, b); add(b, a);

    }

    Tarjan(0, 1);//

    for (int i = 1; i <= n; i++)

    {

        int ans = 2 * (n - 1);//

        if (s[i].size() >= 2)//如果他是割点且割了之后会分成两块那就

        for (int j = 0; j < (int) s[i].size(); j++)

            for (int k = j + 1; k < (int) s[i].size(); k++)

                ans += 2 * s[i][j] * s[i][k];//无向图，要乘2

        printf("%lld\n", ans);

    }

}