题面：[POI2008] BLO-Blockade

大秦为你打开题目传送门

题面翻译

B 城有 $n$ 个城镇（从 $1$ 到 $n$ 标号）和 $m$ 条双向道路。

每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。

把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。

请你对于每个节点 $i$ 求出，把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。

【输入格式】

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示城镇 $a$ 和 $b$ 之间存在一条道路。

【输出格式】

输出共 $n$ 行，每行输出一个整数。

第 $i$ 行输出的整数表示把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。

【数据范围】

$n\le 100000$，$m\le500000$。

题目描述

There are exactly $n$ towns in Byteotia.

Some towns are connected by bidirectional roads.

There are no crossroads outside towns, though there may be bridges, tunnels and flyovers. Each pair of towns may be connected by at most one direct road. One can get from any town to any other-directly or indirectly.

Each town has exactly one citizen.

For that reason the citizens suffer from loneliness.

It turns out that each citizen would like to pay a visit to every other citizen (in his host’s hometown), and do it exactly once. So exactly $n\cdot (n-1)$ visits should take place.

That’s right, should.

Unfortunately, a general strike of programmers, who demand an emergency purchase of software, is under way.

As an act of protest, the programmers plan to block one town of Byteotia, preventing entering it, leaving it, and even passing through.

As we speak, they are debating which town to choose so that the consequences are most severe.

Task Write a programme that:

reads the Byteotian road system’s description from the standard input, for each town determines, how many visits could take place if this town were not blocked by programmers, writes out the outcome to the standard output.

输入格式

In the first line of the standard input there are two positive integers: $n$ and $m$ ($1\le n\le 100\ 000$, $1\le m\le 500\ 000$) denoting the number of towns and roads, respectively.

The towns are numbered from 1 to $n$.

The following $m$ lines contain descriptions of the roads.

Each line contains two integers $a$ and $b$ ($1\le a<b\le n$) and denotes a direct road between towns numbered $a$ and $b$.

输出格式

Your programme should write out exactly $n$ integers to the standard output, one number per line. The $i^{th}$ line should contain the number of visits that could not take place if the programmers blocked the town no. $i$.

样例 #1

样例输入 #1

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

样例输出 #1

1
2
3
4
5
8
8
16
14
8

思路

直接处理出圆方树，然后就发现，破开一个点，其实就是处理出他所有的子树配对的结果，子树配对完后，还要和祖先方向的点配队，然后才是所有点和破开的点的配对，然后由于他是有序数对，所以别忘了乘二。然后这题有一点点卡空间，很烦（

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int MaxV = 1e5 + 10;
const int MaxE = 5e5 + 10;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, m;
Graph< MaxV, MaxE << 1 >G;

inline void Input() {
    read(n, m);
    int u, v;
    for(int i = 1; i <= m; i++) {
        read(u, v);
        if(u == v) continue;
        G.AddEdge(u, v);
        G.AddEdge(v, u);
    }
}

int dfn[MaxV], low[MaxV], cntd;
stack<int >st;
int cntc;
vector<int >T[MaxV << 1];

void Tarjan(int u, int fa) {
    dfn[u] = low[u] = ++cntd; st.push(u);
    if(u == fa && G.head(u) == 0) {
        return ;
    } int ch = 0;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(!dfn[v]) {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                ++cntc; int now;
                do {
                    now = st.top(); st.pop();
                    T[cntc + n].push_back(now);
                    T[now].push_back(cntc + n);
                }while(now != v);
                T[cntc + n].push_back(u);
                T[u].push_back(cntc + n);
            }
        }
        else if(v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

ll sz[MaxV << 1];
ll ans[MaxV << 1];

void Dfs(int u, int fa) {
    for(auto &v : T[u]) {
        if(v == fa) continue;
        Dfs(v, u);
        ans[u] += 2LL * sz[u] * sz[v];
        sz[u] += sz[v];
    }
    if(u <= n) sz[u] += 1;
    ans[u] += 2LL * (sz[u] - 1) * (n - sz[u]);
}

inline void Work() {
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) Tarjan(i, i);
    Dfs(1, 1);
    for(int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i] + 2 * (n - 1));
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}