这场CSP前两题太水了，大样例也太水了，很可能挂分。 我不知道我挂了没有，前两题我做了<1h，然后第三题思考了2h无果转为写暴力，第四题思考1h没时间写爆力了。
T1我做复杂了，肯定是先排序，然后顺序对每个右端点考虑合法的最左端点。但是我没注意到左端点有单调性，看到这样线段树二分可以做后直接开写了（大概开题后20min通过的大样例）。
如果注意到，可以直接使用双指针维护，没有这么麻烦。
这种题不要先考虑暴力维护，看看有没有什么性质在说，不然可能会浪费很多时间。
T2一切正常，希望我的floyd没有写错。
T3一方面是我做太久思路理不清了。
首先预处理\(nxt_i\)表示i后最后一个xj-xi<=k的，\(pre_i\)同理。
我在赛上观察到有两种最短路等价于从l开始一直跳nxt到r的路径与从r开始一直跳pre到l的路径差异为一，且差异的坐标差为1，根据这个写了一个\(O(n^2 \log n)\)的倍增，暴力枚举点对统计。
我赛上一直没有往枚举差异(i,i+1)这方面想，而是尝试从特殊性质中找到正解，成功的在想出AB性质后一无所获。最后由于B性质没有大样例，我只打了A。
在枚举(i,i+1)后，可以发现前驱只能是\(pre_{i+1}\)，后继只能在\(nxt_{i}\)，并且前驱之前和后继之后只能一直跳pre,nxt。
那么可以预处理i及pre的总点数cl，cr同理，答案\(cl \times cr\)，加起来即可。
赛后30min就做出来了，赛上2h想偏了...
这就说明在思考题目时，要评估自己想法的可行性，找最可行的方法做，若发现不太可行在用其他方法。
T4我想到了二分，但是没有想到后面怎么做。
首先二分最大值x，check选取最小点数是否大于k。
看了下题解，发现是考虑直径，为什么呢？因为我们想尽可能的堵住更长的路径，而直径恰好是最长的一条。这样就会有很好的性质：
- 直径上至少存在一个点被选定
- 一个点到直径外的路径<=到直径端点的路径
令直径长度为m。
根据性质1，我们可以发现我们可以枚举直径来覆盖所有情况，这也是我们更加愿意往直径想的原因。
根据性质2，可以发现只要考虑了直径两端，就考虑了两端及其子树的情况。
所以选取直径上第x+1和第m-x个点一定是最优的。
这样这个问题可以分成两种情况讨论： - [x+1,a]和[b,m-x]被选定,(a,b)没有
我们可以枚举从a开始一直选到l，处理出l可以覆盖到的最右子树l'，算出要想使第l'+1子树被覆盖，从右往左覆盖到r，r的最大值。然后统计答案。 - [x+1,m-x]全部被选定
枚举另一个联通块在哪个子树内。然后这个子树的覆盖情况一定是下图:
相当与选择一个子树，与父亲断开联系，分别求两部分的最小个数。
可以处理去掉u子树后，u的最浅未被选择的祖先。则：
其中1部分简单递推即可，2部分设\(dp_{u,d}\)表示在u子树距u最近距离为d的最少点数，然后用长剖维护转移即可。 然后这道题就做完了。
希望不要挂分...