机器人 题目大意 现在机器人有一种移动方式，问机器人从某一个起点到达 lil_ili rir_iri 位置。 题解思路 思考一 nnn个点, nnn 条边的图是什么图 ？很明显这是一个基环树。这样我们在求解距离的时候似乎可以转换为环上的两点之间的距离，这样通过一系列离线的操作，可以在 O(n)的时间下求出来。 思考二 现在我们从 p0p_0p0 出发， 走到 li,ril_i, r_ili ,ri ,这会有什么性质， * 首先出去最后一次移动到的位置，其他的位置都产生了相应的影响。这样我们可以找到开始位置 p1p_1p1 * 还有没有其他性质？设最后一步是向右走，那么 lil_ili 位置一定是白色的。最后一步是向左走 rir_iri 的位置一定是黑色。 * li∼p1l_i \sim p_1li ∼p1 这个位置每一个向右的位置相当于一次转向。在pi∼rip_i \sim r_ipi ∼ri 的位置也是类似。那这个有什么性质呢？我们定pip_ipi 有一个初始方向 a0a_0a0 ,结束的方向为 a1a_1a1 ,如果两个方向相反，那么可以说明左区间的右转向和右区间的左转向数目相同。如果两个方向相同，最终向右走，那么左区间的右转向比右区间的左转向多一个，向左走也类似。 参考代码