感觉完全没有思维能力了啊 QAQ，断断续续想了好久，记录一下心路历程吧。这个思路好像不是很好的样子，建议找题解的同学移步题解区。
一开始读错题了，胡了个离线询问 + 线段树操作的假做法。
后来打算开始写之前明确细节的时候发现寄了，重新读题之后，第一想法肯定是找一下这个图有什么性质。
首先我们肯定好奇 \(u\rightarrow v\) 的最短路长成什么样子。肯定先猜只会向左对吧，然后随便构一下就发现这是不对的，有的时候我们先向右到一个大中转点再向左走会更好。
然后就猜每条最短路里这个中转点只会有一个，也就是说，\(u\rightarrow w\rightarrow v(w>u>v)\)。
我们不妨记 \(w\) 是 \(u\rightarrow v\) 路上的最右点。我们现在想证明一定是先一路右走，再一路左走。这个确实是可以证的，但是我不想码那么多字。
我们现在明确了这个最短路上点的范围，接下来还想知道这个最短路具体是怎么走的。
我们考虑一个 \(u\rightarrow v\) 并且只能向左走，容易发现不超过 \(x\) 步就能到达的点形成一个区间。这个和国旗计划很像，我们考虑把倍增作为解法备选项。现在，只要我们确定最右点 \(w\)，我们就有了一个解法了。
那么，这个最右点 \(w\) 随着 \(u\) 或者 \(v\) 变化是怎么变化的呢？我首先猜了一手单调性，证了一下发现可能是对的。但是目前手头的性质仍然不够我们给出一个很好的算法。
我猜测这个 \(w\) 不会很多。
这个时候 云浅知处 又过来嘲讽了我还恶意给我透露做法
标签：这个,一个,PKUSC2018,短路,最右点,穿越,星际,我们,rightarrow From： https://www.cnblogs.com/PYD1/p/17337616.html