题解：P9019 [USACO23JAN] Tractor Paths P

· · 题解

使用 Qwen3-MAX 渲染 LaTeX。

好的，我已经按照你的要求，仅对格式进行了规范化处理，包括：

下面是处理后的版本：

第一问，这是一道比较经典的题目，CF983E 是这一问的树上版本。发现从左往右走有一个性质：如果点 i < j，那么 j 必然可以走到 i 能达到的最右点，同时可能走到更后面的点。使用倍增，记录从左往右走 2^i 步的点，然后就做好了。

第二问，我们考虑哪些区间会被走到。指定这一特殊区间 S，发现要满足

\operatorname{dis}(u, s) + \operatorname{dis}(s, v) = \operatorname{dis}(u, v),

其中 L = \operatorname{dis}(u, v) 为定值。

那我们考虑枚举不同的 \operatorname{dis}(u, s) 的情况。我们设从左往右走 i 步到达的最优点称为 R(i)，从右往左称为 L(i)。当 \operatorname{dis}(u, s) = i，\operatorname{dis}(s, v) = L - i 时，发现 s 满足

L(i) \leq s \leq R(L - i).

虽然 a \sim R(i) 需要的步数可能不是 i，但是交区间一定满足 \operatorname{dis}(u, s) = i，\operatorname{dis}(s, v) = L - i，要不然 \operatorname{dis} 不是最短路。所以不同的 i 对应的区间不会相交。

现在我们需要统计在所有区间内特殊点的数量，也就是这个式子：

设 \operatorname{cnt}(l, r) 为区间 [l, r] 的贡献，则答案为：

\operatorname{cnt}(a, a) + \operatorname{cnt}(b, b) + \sum_{i=1}^{L-1} \operatorname{cnt}(L(i), R(i)).

前两项直接判断一下，后面的拆成前缀和。令 1 \sim i 的特殊点数量为 \operatorname{sum}(i)，则：

\sum_{i=1}^{L-1} \operatorname{sum}(R(i)) - \sum_{i=1}^{L-1} \operatorname{sum}(L(i) - 1).

我们发现这个 i 每次 +1，其实我们倍增时虽然是一次走 2^i 步，但也可以看成一步步走的。所以我们倍增的时候维护一段 \operatorname{sum}(i) 的值，就做完了。