有一张 个点 条边的简单无向连通图，点的编号分别为 ，每条边长度均为 ，有 次询问，每次给定 ，求 定义 为点 之间的最短路径经过的边数。
显然有：
现在变成在 处求和； 也变成区间 ；这样离线出来做单点到根的链加链查（考虑深度的实际意义），这样就能做到 。
请见之前的图论杂题选讲。
我们找到 到每一个点的最短路，显然这些最短路构成一颗树。
先上结论：求出不穿过这棵树的边的 到 的简单路径中最短的一条即可。
必要性：假设存在一条合法的最短路穿过了这棵树的边，那么它肯定要再次穿过，那么中间的部分可以根据最短路树的性质松弛掉；充分性：显然包含了每个关键点。
我们把每个点拆成四个，连一个四边形，这样就能描述不能穿过（连转角都可以），然后跑 dij 即可。
我们争取和程序轮流把同一列往上叠，把原图分成几个部分，这样就能获得很高的分数（我获得了 66 分，是除了满分之外最高的）。
下赢它就行了。我们考虑让两个 ai 对下；先后手问题可以先在旁边放一个解决；出现不同后，人为微调就行了。
首先我们可以发现一个重要的事实——我们可以从左到右、从高到低放这些积木，每块积木可以放在最右边作为新的边界——没有贡献；或者是放在之前一个曾作为边界的高度边上，贡献为 。
于是我们有了一个 的状压 DP。要想继续优化，就必须压缩状态；而压缩状态的同时保证无后效性的最好方法就是费用提前计算。
先从高到低排序，设 表示目前考虑到了高度 、使用了 个作为非边界的可达集合（用 bitest 维护）；同时记录高度对应数量的前缀和为 ，限制条件是 ，于是有：
前半部分代表我不将当前高度作为边界；最后的答案数组就是 。复杂度 ，不可过。
优化转移：我们发现这个转移的第二部分有点类似于完全背包的形式，直接优化掉即可做到 。
考场上仅最后一步没想到，于是只有 40 分，tmd。
这一类题目有一个非常厉害的普遍做法：
二分答案，然后把这个答案作为边界去搜索，达到上界就退出搜索。
先考虑 的情况：我们把所有类别内的元素排序，并把类别按照它的第一个元素大小来排序，然后直接爆搜加剪枝，复杂度就是对的了；广搜的话细节会非常多，但是也是对的。
然后考虑如何转化为 的情况，我们考虑找到只有一个类型不是选前 个的方案总前 大的，这个也可以二分，然后每个类型分别做；然后我们发现问题就转化为了 的情况。
我是这题的 AHSFNU OJ 最有解啦啦啦。
易得：序列合法当且仅当不存在 使得 。设 表示长度为 的合法序列的个数。如果我们第一个位置放了 ，那么显然我们得先把 都紧接着放下来，因为如果先放了其他的，那么一定会冲突。于是可以得到：
然后我们直接从左向右扫描，找到第一个起飞的位置，并把答案加上这样一个数：
是右手边的系数，这个简单，递归计算即可；关键是如何求这个 。注意到：
我们只需付出 的时间；这是符合启发式分裂的式子的（把过程看作是一次递归，每一次的代价刚好是小的那一边）。
不会
直接退火即可获得 60 分。