官方题解只能做到 $O(n+r^3)$？玩的太差了。可以把这题做到每组 $O(n+r^2)$ 时间、$O(n)$ 空间，其中 $r$ 是环上原始编号点的数量；如果是树，或者初始白点已经把 Alice 与环隔开，则只需要 $O(n)$。

关键改进在环上：公开题解中的实现枚举白色扩张来源及左右阻断位置，存在三重循环；下面把两个阻断位置的联合优化降为线性，从而将环上的复杂度由 $O(r^3)$ 降到 $O(r^2)$。整个算法不展开长链，也不二分答案。

树的等效需求

输入中的一条链包含 $l$ 个新增点，因此把它看作长度为 $w=l+1$ 的边。所有新增点既不是初始白点，也不是目标点，可以直接在压缩后的带权图上计算。([QOJ][2])

先考虑一棵有根树。对于顶点 $u$，维护三个量：

• $d_u$：其子树内最近初始白点到 $u$ 的距离，不存在则为 $\infty$。
• $c_u$：假设 $u$ 已经是黑色，Bob 为了守住其子树，最少需要提前行动多少次。
• $f_u$：把该子树接到父边上时，传给父亲的等效需求。

初始白点是边界，递归到这里直接停止，令 $d_u=f_u=0$。这样也自动处理了 $S\cap T$：已经是白色的目标点不需要再考虑。

对于其他顶点，假设父亲已经是黑色，父边长度为 $w$。Bob 有两种选择。

一种是抢在 Alice 之前占领 $u$。Alice 第 $w$ 次行动就能到达 $u$，此前 Bob 只有 $w-1$ 次正常行动，因此需要提前至少 $\max(0,d_u-w+1)$ 次。

另一种是允许 Alice 占领 $u$，然后守住下面的所有分支。如果 $u\in T$，这种选择不可行，令 $c_u=\infty$；否则，Alice 到达 $u$ 后，Bob 还有本轮的行动机会，所以沿父边前进的过程总共提供了 $w$ 次行动，需要提前 $\max(0,c_u-w)$ 次。

取较小者，就得到 $f_u=\min(d_u+1,c_u)$，这棵子树对父亲的贡献为 $\max(0,f_u-w)$。

不同儿子分支的准备工作互不共享，而 Alice 可以始终攻击准备不足的那个分支，因此这些贡献必须相加。于是，对非初始白点，有 $c_u=\sum_v\max(0,f_v-w_{uv})$；若 $u\in T$，则把 $c_u$ 改为 $\infty$。同时正常维护 $d_u=\min_v(d_v+w_{uv})$。

这也给出了归纳证明：每个分支既可以独立守住，又可以由 Alice 单独攻击，故分支需求恰好相加；父边上的两种处理方式则分别对应“提前占领入口”和“允许进入后防守”。

真正的起点已经是黑色，答案是 $c_1$，不能再用 $d_1+1$ 截断。 若 $1\in T$，Alice 从一开始就已经获胜，直接输出题目规定的上限。

环的归约与二次复杂度

先剥叶找环。如果环上存在初始白点，那么递归遇到白点就停止，Alice 所在的部分已经是树，可以直接使用上述 DP。若环上没有白点，但从 $1$ 到环的必经路径上有白点，也同样退化为树。

下面只讨论真正需要处理环的情况。

设 Alice 进入环的位置为 $v_0$，按环序记作 $v_0,v_1,\ldots,v_{r-1}$，并令 $v_r=v_0$。边 $(v_i,v_{i+1})$ 的长度为 $w_i$，坐标定义为 $x_0=0$、$x_{i+1}=x_i+w_i$。

暂时假设 $v_0$ 已经是黑色，并忽略挂在 $v_0$ 上的树。对其他每个环点，删掉环边后，用树形 DP 求出挂树的两个参数 $c_i,d_i$。

这里必须保留的是 $c_i$，而不是已经截断的 $f_i$：$c_i$ 表示允许这个环点变黑后，防守挂树需要多少准备；使用 $d_i$ 抢占环点，则要放到“白色扩张进入环”的方案中统一考虑。

用前后缀概括未被阻断的部分

假设 Alice 沿正向经过 $v_1,\ldots,v_j$，Bob 不在这些环点上阻断她，而是在各自挂树内完成防守。用 $L_j$ 表示最少提前准备量，用 $U_j$ 表示经过这一段后剩余的行动额度。

初始 $L_0=U_0=0$。扫描到 $j$ 时，先令 $t=U_{j-1}+w_{j-1}$，然后更新 $L_j=L_{j-1}+\max(0,c_j-t)$、$U_j=\max(0,t-c_j)$。如果遇到 $c_j=\infty$，后面的前缀就不允许继续采用这种方案。

反向从 $R_r=V_r=0$ 出发，完全类似地得到 $R_k,V_k$，对应从 $v_0$ 反向经过 $v_{r-1},\ldots,v_k$。

注意两个单调性：$L_j$ 随 $j$ 增大不减；$R_k$ 在 $k$ 从大到小扫描时不减。后面正是利用它们消掉一层枚举。

考虑有效的白色阻断路线。Alice 的黑色区域在环上始终连通，因此只需要防守它的左右边界。删掉无用扩张，并把交叉的左右阻断路线交换后，只需考虑“不上环”“一个来源负责两侧”“两个有序来源各负责一侧”。至多两个来源的分类也是已有环上归约的基础。([3002xz Blog][1])

不上环。 这时全部挂树都必须守住。答案是 $\max_{1\le k\le r}(L_{k-1}+R_k)$。

必要性很直接：对于任意分割位置，左前缀和右前缀的准备发生在互不相交的挂树中，所以需求必须相加。

充分性可以用两遍贪心证明：先正向扫描，每次前缀不足时，只减少当前点的剩余需求；再反向做同样的操作。第一遍在满足正向约束的同时，把准备工作尽量放在靠右的位置，因而对反向前缀最有利。第二遍只会进一步降低需求，不会破坏第一遍的约束。最后的总准备量恰好是上述最大值。

一个来源负责两侧。 枚举白色从 $v_i$ 的挂树进入环，公共路径长度为 $d=d_i$。

设左侧允许 Alice 经过到 $v_j$，右侧允许经过到 $v_k$，其中 $0\le j

左侧需要沿环走 $A=x_i-x_{j+1}$，而 Alice 穿过最后一条边时，Bob 在她到达终点之前只有 $w_j-1$ 次行动。因此左侧可用额度是 $X=U_j+w_j-1$。记净缺口为 $a=A-X$。同理，右侧记 $b=x_{k-1}-x_i-(V_k+w_{k-1}-1)$。

除去两边挂树已经需要的 $L_j+R_k$，额外准备量恰好为

$$ H(d,a,b)=\max(0,\ d+a,\ d+b,\ d+a+b). $$

可以分情况理解这个式子。当 $a,b$ 都非正时，两侧都有富余时间，提前完成一部分公共路径即可，代价为 $\max(0,d+\max(a,b))$。当只有一侧存在正缺口时，必须提前走完公共路径，再补上这一侧的缺口。当两侧都有正缺口时，公共路径仍然只计算一次，但两个分支的缺口都要提前补齐。

所以固定 $i,j,k$ 的代价是 $L_j+R_k+H(d_i,a,b)$。直接枚举就是三次复杂度。

两个来源各负责一侧。 对每个来源 $i$，分别求 $\ell_i=\min_{j< i}{L_j+\max(0,d_i+a)}$ 和 $r_i=\min_{k>i}{R_k+\max(0,d_i+b)}$。两个来源按环序为 $p< q$ 时，代价是 $\ell_p+r_q$。按顺序维护 $\ell_p$ 的前缀最小值即可，无需再枚举来源对。

固定来源后，左右位置可以线性合并

固定 $i$，将一个左端点表示为二元组 $(L_j,a_j)$。

按 $j$ 递增扫描时，第一项不减。如果某个候选的 $a_j$ 不小于之前出现过的最小值，那么之前存在一个候选，其准备量不更多、缺口也不更大。由于 $H$ 对缺口单调不减，当前候选被完全支配，可以删除。

因此，只保留缺口的严格前缀最小值。得到的左候选表中，准备量不减，缺口严格递减。右边按 $k$ 递减扫描，做同样处理。整个过程不需要排序。

现在在线性时间内最小化 $L+R+H(d,a,b)$。

当 $a\ge0$ 时，有 $H=d+a+\max(b,0)$，于是左右完全分离，只需要计算 $d+\min_{a\ge0}(L+a)+\min_b(R+\max(b,0))$。$b\ge0$ 的情况对称处理。

剩下 $a< 0,b< 0$。先考虑 $a\ge b$，此时 $H=\max(0,d+a)$。固定左候选后，只要从右候选中找一个满足 $b\le a$、准备量最小的候选。右表准备量不减、缺口递减，所以符合条件的第一个候选就是最优的。左表的 $a$ 也严格递减，右指针只会向后移动，双指针总计线性时间。再对称处理 $b\ge a$ 即可。

这就把固定来源时的 $O(r^2)$ 左右端点枚举降到了 $O(r)$。所有来源合计 $O(r^2)$，同时也算出了两来源方案需要的 $\ell_i,r_i$。

最后，把整个环重新接回入口 $v_0$：环在入口已黑时的防守需求，加到 $c_{v_0}$ 中；环方向最近白点的距离 $\min_{i\ne0}{d_i+\min(x_i,x_r-x_i)}$，加入 $d_{v_0}$ 的最小值中。然后继续普通树形 DP 即可。

找环、处理挂树和最后一次树形 DP 总共 $O(n)$；每个环上来源只扫描 $O(r)$ 个候选。因此最终是 $O(n+r^2)$ 时间、$O(n)$ 空间。树情形达到读入规模的下界；这里不将基环图的二次上界宣称为已经证明的最优下界。