DAG图上的灭绝树
例题P2597
难点：DAG图上求LCA
其思路是：给每个数多维护一个值dad,用来表示如果此时它要被连入灭绝树中，它应该是哪个点的儿子。一开始将dad清为-1，将开始入度为0的点 pi的dad设为0（太阳）。在拓扑排序取出一个点i的时候连接边 dad[i]->i(此时i的父亲（根节点的父亲前面已经确定）都已经被处理过了，所以dad[i]已经确定（怎么确定的马上会说））。然后更新点i相对应的深度和倍增数组（因为i的祖先们已经在i之前被确定，所以此时的深度和其倍增数组可以唯一确定），接着遍历i的儿子们，如果它的儿子p的父亲dad[p]为0，说明它的父亲还没有被更新过，此时把dad[p]更新为i。否则就将dad[p]更新为LCA（dad[p],i）。这样，在遍历到p的时候它的父节点就被确定下来了。
代码：
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
| #include<bits/stdc++.h>
using namespace std;
int n;
int in[100010];
vector<int>v1[100010];
vector<int>v2[100010];
int f[100010][30], d[100010];
int sz[100010];
queue<int>q;
int t;
int lca(int x, int y) {
if (d[x] > d[y])swap(x, y);
for (int i = t; i >= 0; i--) {
if (f[y][i] == -1)continue;
if (d[f[y][i]] >= d[x])y = f[y][i];
}
if (x == y)return x;
for (int i = t; i >= 0; i--) {
if (f[x][i] == -1 || f[y][i] == -1)continue;
if (f[x][i] != f[y][i])x = f[x][i], y = f[y][i];
}
return f[x][0];
}
void bfs() {
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = 0; i < v1[x].size(); i++) {
int k = v1[x][i];
in[k]--;
if (f[k][0] == -1)f[k][0] = x;
else f[k][0] = lca(f[k][0], x);
d[k] = d[f[k][0]] + 1;
for (int j = 1; j <= t; j++)f[k][j] = f[f[k][j - 1]][j - 1];
if (!in[k]) {
q.push(k);
v2[f[k][0]].push_back(k);
}
}
}
}
void dfs(int x) {
sz[x] = 1;
for (int i = 0; i < v2[x].size(); i++) {
dfs(v2[x][i]);
sz[x] += sz[v2[x][i]];
}
}
signed main() {
ios::sync_with_stdio(false);
memset(f, -1, sizeof(f));
cin >> n;
t = log(n + 1) / log(2) + 1;
for (int i = 1; i <= n; i++) {
while (1) {
int k;
cin >> k;
if (!k)break;
v1[k].push_back(i);
in[i]++;
}
}
for (int i = 1; i <= n; i++) {
if (!in[i]) {
d[i] = 1;
f[i][0] = 0;
q.push(i);
v2[0].push_back(i);
}
}
bfs();
dfs(0);
for (int i = 1; i <= n; i++) {
cout << sz[i] - 1 << endl;
}
return 0;
}
|