P11516 题解

· · 题解

P11516 CCO 2024 Summer Driving

博弈终止节点编号大小，这提示我们直接按双方策略 dp。

先考虑一些部分分。

Sub1：A \le B 时，相当于每次往 1 的方向走 B-A 步，最终一定走到 1。

Sub2：最后的停止点显然由 Bob 决定，线段树优化 dp。

考虑把 Sub2 的做法拓展到树上，设 f_u,g_u 表示 Alice/Bob 在点 u 时的结果。额外地设 f'_u 表示当前在 fa_u，不能走进 u 的子树的结果。

设 F(u,x) 为 u 子树内距离 u 等于 x 的点集，G(u,x) 表示距离 u 不超过 x 的点集（不含祖先），Par(u,x) 表示 u 的 0 \sim x-1 级祖先。

f_u=\max_{v \in F(u,A)}g_v\\ g_u=\min\{\min_{v\in G(u,B)}f_v,\min_{v\in Par(u,B)}f'_v\}

现在你已经会 O(n^2) 了。（在 Alice 无路可走的时候 f_u 的转移有变，但也可以简单计算）

考虑优化 dp。

  1. 对于 f 的转移，不难发现每个 g_v 只会被一个 f_u 用到，均摊 O(n)。
  2. 对于 g 的转移，\min_{v\in Par(u,B)}f'_v 树剖，\min_{v\in G(u,B)}f_v 点分树（吗？）。

发现 k 邻域可以模板点分树，然而扣掉祖先后就不行了。

做法一

但是如果我们要查的是 \sum_{v\in G(u,B)}f'_v 而不是 \min 就能做了。

于是我们在最外层二分一个答案 Ans，编号 \le Ans 的点为白点，编号 >Ans 的为黑点。把 f_u 定义改成“能否走到一个黑点”，g_u,f'_u 同理。

然后我们就要查询类似“u 的 k 邻域内有没有 1”的形式，就可以愉快地上点分树了。

复杂度 O(n \log^3 n)，盲猜过不了。

做法二

假设当前查询的点为 x，在点分树上跳 lca。对于 y。

对于点分树上每个点开一颗树状数组，每个位置维护最大值所在子树和其他子树的最大值。

复杂度 O(n\log^2 n)，比当前次优解快 0.8s。

代码放 LOJ 上了。