$B$ 城有 $n$ 个城镇,$m$ 条双向道路。
每条道路连结两个不同的城镇,没有重复的道路,所有城镇连通。
把城镇看作节点,把道路看作边,容易发现,整个城市构成了一个无向图。
输入格式
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行,每行包含两个整数 $a$ 和 $b$,表示城镇 $a$ 和 $b$ 之间存在一条道路。
输出格式
输出共 $n$ 行,每行输出一个整数。
第 $i$ 行输出的整数表示把与节点 $i$ 关联的所有边去掉以后(不去掉节点 $i$ 本身),无向图有多少个有序点 $(x,y)$,满足 $x$ 和 $y$ 不连通。
数据范围
$n \\le 100000,m \\le 500000$
输入样例:
5 5
1 2
2 3
1 3
3 4
4 5
输出样例:
8
8
16
14
8
思路
不难想到,当 $i$ 为不为割点时,答案为 $2\times(n-1)$。(注意题目中说有序数对。)
故接下来分析 $i$ 为割点时的答案。
设 $\text{tarjan}$ 跑完后的 $\text{DFS}$ 生成树中,第 $u$ 个为根的子树中有 $s_u$ 个点。
考虑到直接考虑答案的一半不好想,故直接考虑答案如何思考。
设 $V$ 为节点集,$subtree_u$ 为以 $u$ 为根的子树中节点的集合,$sum_u$ 为子树中与 $u$ 的祖先不直接连通的点的集合。
令 $j$ 为 $i$ 的子节点,则可以把答案分成如下几个部分:
- $subtree_j$ 和 $V-subtree_j$ 之间的答案
- $subtree_i$ 和 $V-subtree_i$ 之间的答案
- $u$ 和其他所有节点之间的答案。
仔细思考后可以得到答案不重不漏算了两遍,于是这题就做完了。
代码
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\incra\\Desktop\\"
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
bool LAST = false;
istream& operator >> (istream& in,char* s) {
if (LAST) return in;
char ch = in.get ();
while ((isspace (ch) || ch == '\n') && ch != EOF) ch = in.get ();
int n = 0;
while (!(isspace (ch) || ch == '\n') && ch != EOF) s[n++] = ch,ch = in.get ();
s[n] = '\0';
if (ch == EOF) LAST = true;
return in;
}
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
if (y > x) return x = y,true;
return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
if (y < x) return x = y,true;
return false;
}
LL power (LL a,LL b,LL p) {
LL ans = 1;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
const int N = 100010;
int n,m;
vector <int> g[N];
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int s[N];
LL ans[N];
void tarjan (int u,int fa) {
dfn[u] = low[u] = ++timestamp;
stk[++top] = u;
in_stk[u] = true;
s[u] = 1;
int sum = 1;
for (int v : g[u]) {
if (v == fa) continue;
if (!dfn[v]) {
tarjan (v,u);
s[u] += s[v];
tomin (low[u],low[v]);
if (low[v] >= dfn[u]) ans[u] += (LL)s[v] * (n - s[v]),sum += s[v];
}
else if (in_stk[v]) tomin (low[u],dfn[v]);
}
ans[u] += (LL)(n - sum) * sum + n - 1;
}
int main () {
cin >> n >> m;
while (m--) {
int a,b;
cin >> a >> b;
if (a == b) exit (-1);
g[a].pb (b),g[b].pb (a);
}
for (int i = 1;i <= n;i++) {
if (!dfn[i]) tarjan (i,-1);
}
for (int i = 1;i <= n;i++) cout << ans[i] << endl;
return 0;
}