T1:
? 随便推一下就行了，个人感觉拆成二维前缀和更好推
?
T2:
? 显然区间内最大匹配最大，次大匹配次大，以此类推，最优
? 贪心的让每个区间人尽量多也是对的
? 考虑对于一个左端点，如何快速找到最靠右的合法右端点
? （推了半天式子发现增量法并不能用QAQ）
? 直接二分肯定是不行的，因为可以每次只拓展一个，复杂度就会变为\(O(n^2log^2n)\)
? 考虑倍增套二分
? 即：用倍增确定二分区间
? check时暴力sort就行了，复杂度为\(O(nlog^2n)\)
?
T3:
? 首先有个结论：小B只会封掉小A当前所在节点连接的一条路
? 设\(f_i\)表示i点到n点的答案，\(l_{i,j}\)表示(i,j)这条边的长度，\(dis_i\)表示i到n的最短路
? 如果我们可以处理出\(del_{i,j}\)表示删掉(i,j)这条边后i到n的最短路
? 那么就可以用dp：\(f_i=min\{ max(f_j+l_{i,j},del_{i,j}) \}\) 计算答案
? 考虑如何计算\(del\)数组
? 若删的边不在i到n的最短路上，你们\(del_{i,j}\)的值就是\(dis_i\)
? 若删的边在最短路上，且根据前文结论该边一定与i相连，那么我们的问题就转化为了：
? 求不经过最短路树上最后一条边的最短路
? 这个问题比较常见，有两种解决方法：
? 1.树剖 2.并查集（思想）
? 树剖的思路很简单：
? 跑出最短路树，以n为根，计算\(dep_x\)表示x到根的距离
? 因为最后任意点x的答案可以表示为\(max\{dep_a+dep_b+l_{a,b}-dep_x\}\)
? 所以对于每一条非树边(a,b)，可以更新的点为a-b除lca外的所有点，用\(dep_a+dep_b-l_{a,b}\)更新既可
? 并查集的思路就很巧妙了：
? 考虑将非树边按照\(dep_a+dep_b-l_{a,b}\)从小到大排序，那么每个点只需要被更新一次就可以了
原文：https://www.cnblogs.com/Gkeng/p/11839949.html