P4899:[IOI2018] werewolf 狼人题解

解法

这道题是 Kruskal 重构树的裸题。我们先来考虑从\(s\)出发的人形状态,我们要找到一个点点权小于\(L\)的点,就相当于在 Kruskal 重构树上倍增找到最后一个小于\(L\)的点。我们把符合人形规律的 Krukskal 树记为 Tl,其中构造它的方式就是把原来图上所有边的边权赋值为端点的最大值,然后按最小生成树的方式去构造重构树;符合狼形规律的 Kruskal 重构树被记为 Tu,其中构造它的方式就是将端点编号最小值赋为边权,然后按最大生成树的方式构造。之后,我们再到主席树中求交集即可,如果有交集那么查询结果为一个不为零的数,输出\(1\)即可;没有交集那么查询结果即为\(0\),输出\(0\)。

继续阅读P4899:[IOI2018] werewolf 狼人题解

Kruskal 重构树

简述

Kruskal 重构树是图的一种生成树,主要解决一类路径边权限制问题。Kruskal 重构树有按深度单调的性质,所以很容易就可以解决边权的取值限制。

建法

Kruskal 重构树的建造方法和 Kruskal 算法建最小生成树的方法非常类似,但是结构有所不同:Kruskal 重构树将边权变成点权,点权依深度变小。我们假设有一张这样的图:

继续阅读Kruskal 重构树