AK-dream

题目描述

如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力之下。小强建立了一个模型。这世界上有 $N$ 个网络设备,他们之间有 $M$ 个双向的链接。这个世界是连通的。在一段时间里,有 $Q$ 个数据包要从一个网络设备发送到另一个网络设备。一个网络设备承受的压力有多大呢?很显然,这取决于 $Q$ 个数据包各自走的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设备。你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有多少个?

输入格式

第一行包含3个由空格隔开的正整数 $N,M,Q$。 接下来 $M$ 行,每行两个整数 $u,v$ ,表示第 $u$ 个网络设备(从 $1$ 开始编号)和第 $v$ 个网络设备之间有一个链接。 $u$ 不会等于 $v$ 。两个网络设备之间可能有多个链接。 接下来 $Q$ 行,每行两个整数 $p,q$ ,表示第 $p$ 个网络设备向第 $q$ 个网络设备发 送了一个数据包。 $p$ 不会等于 $q$ 。

输出格式

输出 $N$ 行,每行 $1$ 个整数,表示必须通过某个网络设备的数据包的数量。

题解

如果有一条路径必须经过某个点 $x$,那么显然点 $x$ 必为一个割点。

所以建出原图的圆方树,其中每个非叶子的圆点必然代表着原图的一个割点

然后对于一次 $x$ 到 $y$ 的数据传输,必须经过圆方树上 $x,y$ 两点之间的路径,所以使用树上差分统计每个非叶子圆点被经过多少次即可

时间复杂度 $O(n\log n)$

代码

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
#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, Q;
int head[400005], pre[400005], to[400005], sz;

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[400005], low[400005], tme, q[400005], top;
vector<int> e[400005];
int f[400005];

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]);
}
}
}

int d[400005], p[400005][21];

void dfs1(int x, int fa) {
for (int i = 0; i < e[x].size(); i++) {
int y = e[x][i];
if (y == fa) continue;
d[y] = d[x] + 1;
p[y][0] = x;
dfs1(y, x);
}
}

int LCA(int x, int y) {
if (d[x] < d[y]) swap(x, y);
for (int i = 20; i >= 0; i--) {
if (d[x] - (1 << i) >= d[y]) x = p[x][i];
}
if (x == y) return x;
for (int i = 20; i >= 0; i--) {
if (p[x][i] != p[y][i]) {
x = p[x][i]; y = p[y][i];
}
}
return p[x][0];
}

void dfs(int x, int fa) {
for (int i = 0; i < e[x].size(); i++) {
int y = e[x][i];
if (y == fa) continue;
dfs(y, x);
f[x] += f[y];
}
}

int main() {
read(n); nn = n; read(m); read(Q);
for (int i = 1; i <= m; i++) {
int a, b;
read(a); read(b);
addedge(a, b);
}
tarjan(1);
dfs1(1, 0);
for (int l = 1; (1 << l) <= n; l++) {
for (int i = 1; i <= n; i++) {
p[i][l] = p[p[i][l-1]][l-1];
}
}
for (int i = 1; i <= Q; i++) {
int x, y, lca;
read(x); read(y);
lca = LCA(x, y);
f[x]++; f[y]++; f[lca]--; f[p[lca][0]]--;
}
dfs(1, 0);
for (int i = 1; i <= nn; i++) {
printf("%d\n", f[i]);
}
return 0;
}

 评论