[AT TTPC2024 D1C] Segment Tree 题解

把原图放到线段树上。首先拿一棵类似线段树的东西维护一下从区间左端点向右走到区间右端点的最短路。考虑把 拆成 ，其中 是向上走的， 是横着走的（允许 ）， 是向下走的，向上和向下走的过程中允许横着走。设 ，特别地，，表示点 对应树上的结点 。容易发现， 上可能经过的点一定是 所有的祖先（包括其本身）的左右端点，设这个点集为 ，显然 是 的，且容易通过 DP 求出 到 中每个点的距离。 同理，于是处理出路径上可能到达的点，再根据一些可能的情况更新答案即可，详见代码。时间复杂度 。

Submission。