【学习笔记】灭绝树

本来想学支配树,据说和灭绝树就是一个东西,就滚去学了灭绝树。

不过一说到灭绝树,脑海中就会勾勒出一副好久之前的场景,让人怀念……

1 [ZJOI2012] 灾难

给定一个 $\rm DAG$,定义灾难值:在一个节点被删去后以它为根从上到下逐步删去入度为 $0$ 的点,最终被删去的点的数量。求每个点的灾难值。

$n \leq 100,000$

不说构造方面的东西了,直接考虑怎么做。直接建一棵树, $fa_x$ 记录的是这么一个点 $u$,表示如果 $u$ 挂了那么 $x$ 肯定会挂且 $dist(u,x)$ 最小。然后考虑这个东西实际上就是每个 $x$ 的入边的另一个端点在这棵树上的 $\rm LCA$ ,于是考虑边 topsort 边建树。然后子树大小 $-1$ 就是答案。

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
queue <int> q ;
struct Edge{
int to, next ;
}E[MAXN << 1], e[MAXN << 1] ;
int head[MAXN], Head[MAXN], sz[MAXN], cnt1, cnt2 ;
int N, deg[MAXN], dep[MAXN], fa[MAXN], anc[MAXN][20] ;

void add1(int u, int v){
e[++ cnt1].to = v, e[cnt1].next = head[u], head[u] = cnt1 ;
}
void add2(int u, int v){
E[++ cnt2].to = v, E[cnt2].next = Head[u], Head[u] = cnt2 ;
}
void dfs(int u){
sz[u] = 1 ;
for (int k = Head[u] ; k ; k = E[k].next)
dfs(E[k].to), sz[u] += sz[E[k].to] ;
}
int lca(int u, int v){
if (dep[u] < dep[v]) swap(u, v) ;
int dif = dep[u] - dep[v] ;
for (int j = 18 ; j >= 0 ; -- j)
if (1 << j & dif) u = anc[u][j] ;
if (u == v) return u ;
for (int j = 18 ; j >= 0 ; -- j)
if (anc[u][j] != anc[v][j])
u = anc[u][j], v = anc[v][j] ;
return anc[u][0] ;
}
int main(){
ios :: sync_with_stdio(false) ;
cin.tie(0), cout.tie(0), cin >> N ;
for (int i = 1 ; i <= N ; ++ i) fa[i] = -1 ;
for (int i = 1, j, x, y ; i <= N ; ++ i){
cin >> y ;
while (y) add1(y, i), deg[i] ++, cin >> y ;
}
// for (int i = 1 ; i <= N ; ++ i) cout << deg[i] << " " ;
for (int i = 1 ; i <= N ; ++ i)
if (!deg[i]) fa[i] = 0, q.push(i) ;
while (!q.empty()){
int n = q.front() ;
// cout << n << endl ;
q.pop(), add2(fa[n], n) ;
anc[n][0] = fa[n], dep[n] = dep[fa[n]] + 1 ;
for (int i = 1 ; i <= 18 ; ++ i)
anc[n][i] = anc[anc[n][i - 1]][i - 1] ;
for (int i = head[n] ; i ; i = e[i].next){
if (fa[e[i].to] == -1) fa[e[i].to] = n ;
else fa[e[i].to] = lca(n, fa[e[i].to]) ;
if (!(-- deg[e[i].to])) q.push(e[i].to) ;
}
}
// for (int i = 1 ; i <= N ; ++ i) cout << fa[i] << " " ;
dfs(0) ;
for (int i = 1 ; i <= N ; ++ i)
cout << (sz[i] - 1) << '\n' ;
return 0 ;
}

还是很简单的吧?

2 CF757F Team Rocket Rises Again

一道例题?

给定一个 $n$ 个点,$m$ 条边的带权无向图和起点 $\rm S$。选择一个点 $u$ $(u\not =\rm S)$,使在图中删掉点 $u$ 后,有尽可能多的点到 $\rm S$ 的最短距离改变。

$n\leq 200,000$

在发现求完一遍最短路这个图变成 DAG之后,这道题就变成了一道傻题。

哦,忘了,有个坑点。他可能给的这个图一开始不连通,所以要判一下 vis

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
void add(int m, int u, int v, int w){
E[m][++ cnt[m]].to = v, E[m][cnt[m]].val = w,
E[m][cnt[m]].next = head[m][u], head[m][u] = cnt[m] ;
}
void dfs(int u){
sz[u] = 1 ;
for (int k = head[2][u] ; k ; k = E[2][k].next)
dfs(E[2][k].to), sz[u] += sz[E[2][k].to] ;
if (vis[u] && u && u != S) ans = max(ans, sz[u]) ;
}
int lca(int u, int v){
if (dep[u] < dep[v]) swap(u, v) ;
int dif = dep[u] - dep[v] ;
for (int j = 18 ; j >= 0 ; -- j)
if (1 << j & dif) u = anc[u][j] ;
if (u == v) return u ;
for (int j = 18 ; j >= 0 ; -- j)
if (anc[u][j] != anc[v][j])
u = anc[u][j], v = anc[v][j] ;
return anc[u][0] ;
}
int main(){
cin >> N >> M >> S ; int u, v, w ;
for (int i = 1 ; i <= M ; ++ i)
scanf("%d%d%d", &u, &v, &w),
add(0, u, v, w), add(0, v, u, w) ;
q.push(S) ; vis[S] = 1 ;
fill(dis + 1, dis + N + 1, Inf), dis[S] = 0 ;
while (!q.empty()){
int n = q.front() ; q.pop() ; vis[n] = 0 ;
for (int k = head[0][n] ; k ; k = E[0][k].next){
if (dis[E[0][k].to] > dis[n] + E[0][k].val){
dis[E[0][k].to] = dis[n] + E[0][k].val ;
if (!vis[E[0][k].to])
vis[E[0][k].to] = 1, q.push(E[0][k].to) ;
}
}
}
for (int i = 1 ; i <= N ; ++ i)
for (int j = head[0][i] ; j ; j = E[0][j].next)
if (dis[i] + E[0][j].val == dis[E[0][j].to])
add(1, i, E[0][j].to, 0), deg[E[0][j].to] ++ ;
fill(vis, vis + N + 1, 0) ;
for (int i = 1 ; i <= N ; ++ i) fa[i] = -1 ;
q.push(S), fa[S] = 0 ;
while (!q.empty()){
int n = q.front() ;
q.pop(), vis[n] = 1, add(2, fa[n], n, 0) ;
anc[n][0] = fa[n], dep[n] = dep[fa[n]] + 1 ;
for (int i = 1 ; i <= 18 ; ++ i)
anc[n][i] = anc[anc[n][i - 1]][i - 1] ;
for (int k = head[1][n] ; k ; k = E[1][k].next){
int ww = E[1][k].to ;
if (!(~fa[ww])) fa[ww] = n ;
else fa[ww] = lca(fa[ww], n) ;
if (! -- deg[ww]) q.push(ww) ;
}
}
dfs(0) ; cout << ans << endl ; return 0 ;
}

3 吐槽

这东西在 Luogu 上也能算紫色的?

4 一点回忆

那是 18 年的 4 月。想来已经是前年了,有些伤感。

当时金牌教练让 rqy 给我们出题考试,题目如下:

T1是个有点 tricky 的最小字典序最大独立集,T2就是个灭绝树的板子,T3是个 DLX 的板子。然而当时大家最高分只有 $60$ 分也是有点惨惨。

还记得当时大家几乎都在认真地做 T2,我在做 T1 的前 60 分。然而最后 T1 还是因为边表没开两倍而 RE 挂了 40,大家 T2 都是枚举每个点然后再去 topsort , 可惜当时我连 topsort 也不会。

然后大家考完之后,听完 rqy 讲题就开始研究 T2,发现原来就是“[ZJOI]灾难”那题。然后大家就都去做了那道题。

还记得wx在考场上已经想出了几近正解,当时自己只会膜。

到现在为止,“灾难”这题在Luogu的题解区,地一篇题解依旧是wx的,他的前三条评论依旧是我的。

感觉……有点伤感。不知道是不是机房太冷的缘故,感到大脑有些麻木。是啊,rqy不再是当年的rqy了,LCEZ55级机房也不是之前那个LCEZ55级机房了,也搬到了新校。总之,一切都变了。

倒不是说改变不好,只是那些夕阳下的场景总是让现如今孑然一身的我感到有些无所适从。

看来我就是那被遗忘在时光里的老人了吧。

要说启迪什么的,大概就是不要再等到失去之后发现自己当时有多么愚蠢。

以前总是不理解为什么 rqy 要为了没有人陪他学OI而哭,现在才发现,“哦,原来是这样子的感觉啊”。

『 初闻不解戏中意,如今已是戏中人。』