翻译：一个原本连通的无向图，可以删除图中的一个点，求因为删除这个点所导致的不连通的有序点对的数量。或者说，删去这个点之后，各个连通分量的大小的乘积之和？

当然是考虑新学的Tarjan法求割点。一遍Tarjan给每个点记录他是不是割点。然后第二遍的时候对每个割点，统计它分割出的各个子树（及其父亲，假如有的话）这些连通块之间的贡献。

注意无向图是不需要栈的，因为无向图不存在横向边的说法。

错误代码：

#include
    
     using namespace std;typedef long long ll;const int MAXN = 100005;int n;vector
     
       G[MAXN];vector
      
        T[MAXN];int dfn[MAXN], low[MAXN], dfncnt;bool cut[MAXN];int siz[MAXN];ll ans[MAXN];void tarjan(int u, int p) {    low[u] = dfn[u] = ++dfncnt;    siz[u] = 1;    cut[u] = false;    if(p != -1)        T[u].push_back(p);    int ch = 0;    for(auto v : G[u]) {        if(!dfn[v]) {            tarjan(v, u);            T[u].push_back(v);            low[u] = min(low[u], low[v]);            siz[u] += siz[v];            if(p != -1 && low[v] >= dfn[u])                cut[u] = true;            else if(p == -1)                ch++;        } else            low[u] = min(low[u], dfn[v]);    }    if(p == -1 && ch >= 2)        cut[u] = true;}bool vis[MAXN];void dfs(int u, int p) {    vis[u] = 1;    for(auto v : T[u]) {        if(!vis[v])            dfs(v, u);    }    if(cut[u]) {        ll sum = 0;        ans[u] = 0;        for(auto v : T[u]) {            if(v == p) {                sum += n - siz[u];                ans[u] -= 1ll * (n - siz[u]) * (n - siz[u]);            } else {                sum += siz[v];                ans[u] -= 1ll * siz[v] * siz[v];            }        }        ans[u] += sum * sum + 2ll * sum;    } else        ans[u] = 2ll * (n - 1);}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);#endif // Yinku    int m;    scanf("%d%d", &n, &m);    for(int i = 1, u, v; i <= m; ++i) {        scanf("%d%d", &u, &v);        G[u].push_back(v);        G[v].push_back(u);    }    tarjan(1, -1);    dfs(1, -1);    for(int i = 1; i <= n; ++i) {        printf("%lld\n", ans[i]);    }    return 0;}
      
     
    

错误原因：某个节点u的子树v中可能出现了反向边（反向到u之前），这棵子树则和u节点的父亲节点等形成了连通块，假如要分段统计，则要在u节点标记哪些子树才是真正会被分开的子树。

那么在这个问题里面对于根节点来说，每棵子树是必定会被分开的，可以统一处理掉。

#include
    
     using namespace std;typedef long long ll;const int MAXN = 100005;int n;vector
     
       G[MAXN];int dfn[MAXN], low[MAXN], dfncnt;ll ans[MAXN];int siz[MAXN];void tarjan(int u, int p) {    low[u] = dfn[u] = ++dfncnt;    siz[u] = 1;    ll sum=0;    int ch = 0;    for(auto v : G[u]) {        if(!dfn[v]) {            tarjan(v, u);            low[u] = min(low[u], low[v]);            siz[u] += siz[v];            if(low[v] >= dfn[u]){                ans[u]+=sum*siz[v];                sum+=siz[v];            }        } else            low[u] = min(low[u], dfn[v]);    }    ans[u]+=(n-1-sum)*sum;    ans[u]+=(n-1);    ans[u]*=2ll;}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);#endif // Yinku    int m;    scanf("%d%d", &n, &m);    for(int i = 1, u, v; i <= m; ++i) {        scanf("%d%d", &u, &v);        G[u].push_back(v);        G[v].push_back(u);    }    tarjan(1, -1);    for(int i = 1; i <= n; ++i)        printf("%lld\n", ans[i]);    return 0;}