# 1. LCT 在动态图连通性、动态 MST、动态路径的工业应用。 A LCT 的路径查询是 O(n) B LCT 只能处理静态树 C LCT 支持 link/cut/makeroot/路径查询，均摊 O(log n)，用于动态连通性、动态 MST 与动态路径 ✓ 正确答案 D LCT 不支持动态 MST
# 2. LCT access 的摊还分析中每次 access 的虚实边切换次数均摊 O(log n)，与 splay 势能如何合并 A access 的切换次数是 O(1) 最坏 B 虚实切换次数用轻边计数证明均摊 O(log n)，与 splay 的 Σlog(size) 势能合并得到整体 O(log n) 摊还 ✓ 正确答案 C access 复杂度与 splay 势能无关 D access 每次切换 O(n) 条边
# 3. LCT 的 access/rotate/splay/link/cut 操作在动态树路径查询的 O(log n) 摊还实现。 A 路径查询是 O(n) B link 无需 makeroot C access 只是普通 splay D 路径查询用 makeroot(u)+access(v)+splay(v) 把 u-v 路径聚到 v 的 splay，各操作均摊 O(log n) ✓ 正确答案
# 4. LCT 的 preferred path 与 preferred edge 在 expose 操作的工程细节。 A preferred edge 是虚边 B preferred edge 指最近访问的实边，preferred path 是实边链，access 把到根路径全部变为实边并调整虚实划分 ✓ 正确答案 C access 不改变虚实划分 D preferred path 是固定不变的
# 5. Top Tree 的 Rake/Compress 树形态化简与边界节点处理。 A Top Tree 只有 compress，没有 rake 操作 B compress 合并路径簇、rake 合并分支/叶节点，边界节点定义簇接口，簇抽象把动态树推广到更一般结构 ✓ 正确答案 C 簇不含边界节点 D Top Tree 与 LCT 等价，无推广
# 6. LCT 的路径懒标记中路径加/乘与 rev 同时存在时标记如何组合与下传，makeroot 后聚合如何更新 A 懒标记不下传也能正确 B 加和乘标记可任意顺序组合 C rev 标记不影响任何聚合 D 加/乘标记按先乘后加组合，rev 反转独立，下传需定义顺序，方向相关聚合在 rev 后需交换 ✓ 正确答案
# 7. Link-Cut Tree 的原理中实链剖分与 Splay 辅助树，access/makeroot 如何维护路径信息？ A LCT 用实链剖分 + Splay 辅助树维护路径，access/makeroot 调整虚实划分并聚合路径信息 ✓ 正确答案 B LCT 用线段树维护实链 C access 不需要 splay D LCT 的 makeroot 不改变路径方向
# 8. LCT 的 makeroot 为什么需要打反转标记（rev），换根操作如何改变 preferred path 的方向，信息聚合如何处理？ A makeroot 需反转路径使 x 变根，用 rev 懒标记交换左右子，方向相关聚合在反转后需交换前后缀 ✓ 正确答案 B rev 标记用于加法懒标记 C makeroot 不需要反转 D 方向相关聚合不受 rev 影响
# 9. LCT 的典型应用中动态连通性、动态树上路径最值与子树操作？ A LCT 不能做动态连通性 B LCT 天然支持子树操作，无需扩展 C findroot 用于求路径最值 D 动态连通性用 link/cut+findroot，路径最值用 makeroot+access 聚合，子树操作需额外维护虚子树信息 ✓ 正确答案
# 10. LCT 维护子树信息的局限中标准 LCT 只能维护链信息，维护子树需要额外记录虚子树信息，如何实现？ A 标准 LCT 聚合只覆盖实链，维护子树需额外记录虚子树贡献并在虚实切换/link 时更新 ✓ 正确答案 B 标准 LCT 天然包含子树聚合 C 虚子树信息不需要更新 D 子树信息与实链信息无关
# 11. Splay 访问序列最优性 (Access Sequence Optimality) 在缓存局部性强的工程实现。 A 访问序列最优性只适用于静态数据 B Splay 树的访问开销与历史无关 C Splay 需要存储平衡因子 D Splay 把访问节点旋到根，访问序列最优性保证任意序列渐近最优，工作集定理使热点节点保持浅层 ✓ 正确答案
# 12. Splay 与 Treap 在 10^8 操作下的实测 cache miss 与分支预测命中率。 A Splay 一定比 Treap 快 B Splay 倾斜访问时热点在浅层缓存命中高，Treap 随机结构稳定、分支预测好，取决于访问分布 ✓ 正确答案 C Treap 倾斜访问时缓存命中更高 D 两者内存布局完全相同
# 13. Splay 与 skip list 在 workload skew 分布下的实测对比。 A Splay 自调整使热点上浮、skew 分布下访问成本低，跳表结构固定无法利用偏斜，故 skew 下 Splay 更优 ✓ 正确答案 B 跳表在 skew 分布下优于 Splay C 两者都自调整 D 跳表能利用访问偏斜
# 14. Splay Top Tree (Tarjan & Sleator) 的 cluster forest 与 Rake/Compress 操作。 A Top Tree 只有簇没有合并操作 B Sleator-Tarjan 用簇（cluster）组织成 cluster forest，Rake/Compress 合并簇，splay 维护使操作摊还 O(log n) ✓ 正确答案 C Rake 合并路径、Compress 合并分支 D Top Tree 与 LCT 完全等价
# 15. Splay 在 Codeforces 14D 与实际工业实现的常数因子差异。 A 竞赛和工业实现常数完全相同 B 竞赛用静态数组模拟节点、无封装、常数小，工业用对象封装、可维护但常数大，同一算法常数可差数倍 ✓ 正确答案 C 工业实现常数更小 D 竞赛 Splay 必须用递归
# 16. Splay 静态最优性 (Static Optimality Theorem) 与工作集定理 (Working Set Theorem) 的工程应用。 A 静态最优性只保证插入最优 B 静态最优性保证 Splay 不差于任意静态最优树，工作集定理说明访问越频繁的节点越浅，适合热点/缓存场景 ✓ 正确答案 C 工作集定理与访问频率无关 D Splay 无法自适应访问分布
# 17. Sleator-Tarjan 的 splay 操作 zig/zig-zig/zig-zag 的势能函数 Φ(T) = Σ log(size(x)) 的严格推导。 A splay 摊还代价是 O(1) B 势能函数任意选择都能证明 C zig-zig 的势能变化不足以支付旋转 D 用 Φ=Σlog(size) 作势能，zig-zig/zig-zag 的势能变化足以抵消旋转代价，累加抵消后每次操作摊还 O(log n) ✓ 正确答案
# 18. Top Tree 与 LCT 的关系中簇（cluster）抽象在更复杂动态树问题中的扩展？ A LCT 是 Top Tree 在链抽象下的特例，Top Tree 用簇抽象扩展到动态子树、动态最小割等更复杂问题 ✓ 正确答案 B Top Tree 是 LCT 的子集 C 两者抽象层次完全相同 D Top Tree 只能处理路径问题
# 19. link/cut 的前置条件中 link 前需 makeroot 确认无环、cut 前需确认父子关系，错误操作如何破坏结构 A link 无需确认是否成环 B link 前 makeroot 并确认不同树（无环），cut 前 makeroot+access 确认父子关系，违反会破坏树形不变式 ✓ 正确答案 C cut 可以任意断开边 D 前置条件不影响正确性
