AK-dream

题目描述

在Byteotia有 $n$ 个城镇。 一些城镇之间由无向边连接。在城镇外没有十字路口,尽管可能有桥,隧道或者高架公路(反正不考虑这些)。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。每个城镇都有一个公民,他们被孤独所困扰。事实证明,每个公民都想拜访其他所有公民一次(在主人所在的城镇)。所以,一共会有 $n*(n-1)$ 次拜访。

不幸的是,一个程序员总罢工正在进行中,那些程序员迫切要求购买某个软件。作为抗议行动,程序员们计划封锁一些城镇,阻止人们进入,离开或者路过那里。正如我们所说,他们正在讨论选择哪些城镇会导致最严重的后果。

编写一个程序:

读入Byteotia的道路系统,对于每个被决定的城镇,如果它被封锁,有多少访问不会发生,输出结果。

输入格式

第一行读入 $n,m (1\le n\le 100\ 000, 1\le m\le 500\ 000)$,分别是城镇数目和道路数目

城镇编号 $1\sim n$

接下来 $m$ 行每行两个数字 $a,b (1\le a<b\le n)$,表示 $a$ 和 $b$ 之间有一条无向边

输出格式

输出 $n$ 行,每行一个数字,为第 $i$ 个城镇被锁时不能发生的访问的数量。

题解

显然,只有被封锁的点为割点时,才会出现无法访问的情况

所以求出所有点双连通分量,对原图建出圆方树,只需要找出对于每个非叶子的圆点(原图中的割点),有多少条圆点到圆点的路径经过它。当这个割点被封锁后,这些路径就无法访问了

把圆点的权值看作 $1$,方点权值看作 $0$,然后维护子树权值和就可以求出答案

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

int n, nn, m;
int head[100005], pre[1000005], to[1000005], sz;
int siz[200005];
ll ans[100005];

void addedge(int u, int v) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v;
pre[++sz] = head[v]; head[v] = sz; to[sz] = u;
}

int dfn[100005], low[100005], tme, q[100005], top;
bool gd[100005];
vector<int> e[200005];

void tarjan(int x) {
dfn[x] = low[x] = ++tme;
q[++top] = x;
int now = 0;
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
if (dfn[x] <= low[y]) {
n++;
int z = 0;
do {
z = q[top];
e[n].push_back(z);
e[z].push_back(n);
top--;
} while (z != y);
e[n].push_back(x);
e[x].push_back(n);
}
} else {
low[x] = min(low[x], dfn[y]);
}
}
}

void dfs(int x, int fa) {
if (x <= nn) siz[x] = 1;
for (auto y : e[x]) {
if (y == fa) continue;
dfs(y, x);
if (x <= nn) {
ans[x] += 1ll * siz[x] * siz[y];
}
siz[x] += siz[y];
}
if (x <= nn) {
ans[x] += 1ll * siz[x] * (nn - siz[x]);
}
}

int main() {
read(n); nn = n; read(m);
for (int i = 1; i <= m; i++) {
int a, b;
read(a); read(b);
addedge(a, b);
}
tarjan(1);
dfs(1, 0);
for (int i = 1; i <= nn; i++) {
printf("%lld\n", ans[i] * 2); //u->v和v->u都要算
}
return 0;
}

 评论