真心巧妙，不看题解准做不出(之前题解都看不懂QwQ)

这道题貌似有许多的做法，都不费，主席树的话不知道怎么搞，于是建了 $3$ 棵线段树，实测是不会炸的。

一道莫队……….

最主要的就是怎么从当前区间推到相邻区间。

假设当前区间为 $[l,r]$ ，目标区间为 $[l,r+1]$ 。那么很显然这样子就会增加：

这些区间，现在我们要做的就是尽快的算出这些区间的答案。

题目要求你做什么就做什么呗。

我们先跑最短路，然后按照最短路的边连网络流的边就好了。

这里我选择跑堆优 $Dij$ ，然后我们枚举每一条边，判断着一条边是否为最短路的边，判断的方式很显然，就是看这条边的起点的 $dis$ 加上边权是否等于终点的 $dis$ 就好。

题目大意就是，有多组询问，每组询问包含两个整数 $x,y​$ ，求出 $x​$ 到 $y​$ 的一条路径，满足这条路径在所有的 $x​$ 到 $y​$ 的路径中，边权最小的边权值最大。

这个很显然我们可以先求出图的最大生成树，那么 $x$ 到 $y$ 的目标路径肯定在最大生成树上，也只能在最大生成树上。

这题真的是裸的网络流……连我这种制杖都可以立刻想到正解。

如果不考虑领地问题的话，这显然是一道很裸的最小割———割断最少的边使 $S$ 和 $T​$ 不连通。

但是现在有了领地的问题……就是说限制了有些格子是一起的，不能被割开。

既然不能被割开，就连一条 $inf$ 的边啊，这样就割不开了啊。

神奇的珂朵莉树，优雅的暴力。

珂朵莉树的主要思想就是对于一段连续的值相同的区间，将其缩为一个结点，然后丢到 $set$ 里面，主要的操作有拆分区间操作…….这货很强大，码量不短但极好写，而且一般不会出什么问题，调试也很方便。

别人都说，什么淀粉质啊之类的轻松水过，然而我有码量恐惧症，不适合如此数据结构(主要也是太弱了QvQ)

实际上这道题可以用贪心解的……但是码量惊人 $QwQ$ 。

于是上网络流吧……这题显然是费用流。

对于每一天，我们将其拆成两个点，一个表示这天的早晨，一个表示这天的晚上。

毒瘤题目，树上带修改莫队板子题。

关于树上莫队和带修改莫队的文章戳这 $QwQ​$ :[算法]莫队&树上莫队

然后就是将其结合在一起了，结合的话炒鸡简单，就是码量增大…