题解：P9019 [USACO23JAN] Tractor Paths P

使用 Qwen3-MAX 渲染 LaTeX。

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

下面是处理后的版本：

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

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

其中 $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$ 满足

虽然 $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]$ 的贡献，则答案为：

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

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