Borůvka + 隐式图模型实例:主理想

Borůvka 隐式图模型中以主理想为核心的 oracle 实例:布尔格 Zeta 变换 / SOS DP、树形偏序子树最值、DAG 可达性的双主理想。

标签 图论 / 生成树 / Borůvka / 问题模型 / 主理想

本页承接 Borůvka + 隐式图模型,收集 𝑁(𝑖) 能化成 主理想查询的 oracle 实例。布尔格和树形偏序中 𝑁(𝑖) 是一个主理想;DAG 可达性中 𝑁(𝑖) 是原图与反图各一个主理想。其余 oracle 实例见 Borůvka + 隐式图模型实例。

这些实例的 oracle 都归结为主理想上的最值查询:一个主理想读一个 Zeta 表项,两个主理想分别查询后合并;排除当前分量仍用来自不同分量的前两名摘要。

以下沿用主模型页的记号:𝑃(𝑖,𝑗) 表示边存在,𝑣𝑖 表示点权。

实例一:布尔格(Zeta 变换 / SOS DP)

每个点 𝑖 对应一个 𝐵 位掩码 𝑎𝑖,掩码按子集关系构成偏序。令

𝑞(𝑖)≝(2𝐵−1)xor𝑎𝑖,𝐼(𝑞(𝑖))≝{𝑥:𝑥⊆𝑞(𝑖)}

谓词定义为

𝑃(𝑖,𝑗)≝(𝑎𝑖and𝑎𝑗=0)

由于 𝑎𝑖and𝑎𝑗=0 等价于 𝑎𝑗⊆𝑞(𝑖),所以 𝑁(𝑖) 就是主理想 𝐼(𝑞(𝑖)) 中的点。

沿用可分离边权 𝑤(𝑖,𝑗)=𝑓(𝑣𝑖)+𝑔(𝑣𝑗),固定 𝑖 后只需最大化 𝑔(𝑣𝑗)。对布尔格做 Zeta 变换(SOS DP),预处理出每个掩码 𝑥 的主理想 𝐼(𝑥) 上按 𝑔(𝑣𝑗) 排序的前两名候选,且两项来自不同分量。查询 𝑖 时取 𝑥=𝑞(𝑖),从中选第一个分量不是 𝐶 的候选即可。

每轮重建 Zeta 表的代价是 𝑂(𝐵2𝐵+𝑛),查询 𝑂(1);总复杂度 𝑂((𝐵2𝐵+𝑛)log𝑛),空间 𝑂(2𝐵)。

题目:CF1305G: Kuroni and Antihype:布尔格主理想 + 可分离点权边权的具体实例。

实例二:树形偏序(子树最值)

设每个点 𝑖 对应一棵有根树上的节点 𝑎𝑖,偏序取“后代 ≤ 祖先”。节点 𝑎𝑖 的主理想为

𝐼(𝑎𝑖)≝{𝑥:𝑥≤𝑎𝑖}=subtree(𝑎𝑖)

谓词定义为 𝑃(𝑖,𝑗)≝𝑎𝑗∈𝐼(𝑎𝑖)。此时 𝑁(𝑖)=𝐼(𝑎𝑖),查询就是主理想上的最值。

把树按 DFS 序展开,子树对应一个连续区间。用线段树维护区间内按 𝑔(𝑣𝑗) 排序的前两名(来自不同分量),查询 𝑖 时对区间取前两名摘要即可。

也可以自底向上合并子树摘要,预处理 𝑂(𝑛),查询 𝑂(1);若每轮重建线段树,则每轮 𝑂(𝑛log𝑛)。若 𝑁(𝑖) 是少量子树之并,就合并少量区间。

实例三:DAG 可达性(祖先与后代最值)

给定 DAG 𝐺=(𝑉,𝐸)。把可达关系看作 偏序(允许零长度路径),谓词定义为

𝑃(𝑖,𝑗)≝(𝑖≠𝑗)∧(reach(𝑖,𝑗)∨reach(𝑗,𝑖))

也就是两个不同点在该偏序下是否可比。

固定 𝑖 后,满足 𝑃(𝑖,𝑗) 的点是 𝑖 的其余祖先或其余后代。设 𝐺𝑅 为把 𝐺 的边全部反向得到的反图,记

𝐼𝐺(𝑖)≝{𝑗:𝑗能到达𝑖}

为 𝐺 的可达偏序中由 𝑖 生成的主理想。类似地,𝐼𝐺𝑅(𝑖) 是反图中的主理想,也就是 𝑖 在 𝐺 中的后代集合。两个主理想都包含 𝑖,所以

𝑁(𝑖)≝(𝐼𝐺(𝑖)∪𝐼𝐺𝑅(𝑖))∖{𝑖}

沿用模型页的可分离边权 𝑤(𝑖,𝑗)=𝑓(𝑣𝑖)+𝑔(𝑣𝑗),查询变成

query(𝑖,𝐶)=argmax𝑗∈𝑁(𝑖),comp(𝑗)≠𝐶𝑔(𝑣𝑗)

只要求出这两个主理想中“排除当前分量后的最优候选”,再取较大者即可。

源码位置