「CCO 2024」Summer Driving 题解

题目分析

本题是一个在树结构上的博弈问题。Alice 和 Bob 轮流在树上移动，Alice 每次必须走恰好 $A$ 条未走过的边，Bob 每次可以走最多 $B$ 条边（可以重复走）。Alice 希望最终到达编号最大的城市，Bob 希望到达编号最小的城市。

关键观察

1. 树结构性质：城市和道路构成一棵树，这简化了路径分析
2. 移动规则差异：
   • Alice 必须走恰好 $A$ 条新边
   • Bob 可以走最多 $B$ 条边（可重复）
3. 博弈目标相反：双方有完全相反的目标函数

算法思路

核心思想：二分答案 + 树形DP

我们使用二分答案来确定最终能够到达的城市编号。对于每个候选答案 $mid$，我们判断在双方最优策略下，Alice 能否迫使游戏在编号 $\geq mid$ 的城市结束。

主要数据结构

• 邻接表：存储树结构
• DFS序：用于子树区间操作
• 线段树：支持区间更新和单点查询
• 栈：维护DFS遍历路径

状态定义

• dep[x]：节点 $x$ 的深度
• f[x]：从节点 $x$ 开始，在当前二分值 $mid$ 下 Alice 是否能获胜
• g[y]：辅助状态，处理特殊移动
• h[y]：记录边界条件
• mn0[x]：子树中满足条件的最小深度
• mnf0[x]：关键的最小深度值

算法流程

1. 预处理：

   dep[rt] = 1, dfs_pre(rt);
   

   通过DFS计算深度、DFS序，并建立父子关系

2. 二分框架：

   while (l < r)
       check(mid = l + r + 1 >> 1) ? l = mid : r = mid - 1;
   

3. 检查函数 check(mid)：

   • 按深度从大到小处理节点
   • 对于每个节点 $x$：
     • 计算 mn0[x]：子树中编号 $\geq mid$ 的最小深度
     • 处理特殊移动情况（$A-B$ 相关的移动）
     • 更新线段树维护区间信息
     • 计算博弈状态 f[x]

4. 关键判断：

   • 如果 f[rt] 为真，说明 Alice 可以到达编号 $\geq mid$ 的城市
   • 否则 Bob 可以阻止 Alice 到达这样的城市

复杂度分析

• 时间复杂度：$O(n \log^2 n)$
  • 二分答案：$O(\log n)$
  • 每次检查：$O(n \log n)$（DFS序 + 线段树操作）
• 空间复杂度：$O(n)$

代码亮点

1. 高效预处理：使用DFS序将子树操作转化为区间操作
2. 线段树优化：快速处理区间最小值查询和更新
3. 状态压缩：通过巧妙的状态设计避免重复计算
4. 分层处理：按深度分层处理，保证DP的正确性

总结

本题通过将博弈问题转化为树上的最优化问题，结合二分答案和树形DP，巧妙地解决了双方最优策略下的最终位置问题。算法充分利用了树结构的性质，通过DFS序和线段树优化了状态转移的效率。