T1货物收集

部分分设置

对于的数据，给阶乘级别的搜索算法。

对于的数据，考虑对所有边权排序，然后每次增加的量肯定是某两个边权的差值。模拟增加过程，当满足条件时输出即可。时间复杂度

对于链上的情况，贪心向两端扩展即可。

题解思路

我们考虑经过一条边并不会减少我们的武力值。

我们只需要二分一个我们的武力值，然后O(n)判断一次当前能取到多少货物，就可以了。时间复杂度

T2 货物分组

Notice: 这道题在考试过程中，为了卡掉一些剪枝的暴力，不小心把错误的贪心全部放过去了，正在重造数据。
UPD: T2数据已经重新构造，并且已经重测。为大家带来的不好体验，我表示万分抱歉。

部分分设置

对于10%的数据，我们暴力枚举分组数以及分组情况。

对于30%的部分分，留给暴力DP

对于60%的部分分，我们稍后会介绍一个暴力DP

正解思路

首先考虑一个DP

表示前n个分成m组的最小花费。我们只要枚举之后
其中表示物品代价的前缀和。
这样转移是的。我们考虑使用先付代价来DP.

表示前n个分成若干组的最小代价。那么我们枚举k之后

其中表示l~r的重量和加上其中最大值减最小值。

这样是的。

我们发现我们在转移过程中，可以用一个单调栈来维护最大值和最小值的变换，然后用线段树维护区间最值，就能每次更新答案。

时间复杂度

T3 地形计算

部分分设置

对于的分数，给直接暴力枚举点然后判断的做法。

对于的做法，给 或可能存在的

解题思路

首先我们考虑一个很Naive的暴力，从每个点往下搜四层，如果回到了这个点，那么说明有一个四元环，我们把中间经过的点累加进答案。

这样每次扩展 个点，扩展四次，时间复杂度，如果你的实现比较美观的话，是的，不过因为算法本质相同，并没有设置这两种实现方式的分数区分。

我们考虑另一种做法，不扩展四层，而是每次扩展两层，用一种MIM(Meet In Middle)的方式统计答案，时间复杂度就降到了 ，可以拿到60分。

似乎已经没有更好的方法了，但是我们考虑对于60分的做法，我们切换枚举顺序，从度数最大的点开始枚举。

每次枚举完毕以后，删去度数最大的点，然后重复这个过程，也能统计出答案。正确性显然，我们考虑这个做法的复杂度。每次都使减小1，那么复杂度为 看起来没什么用，只是多了一个的常数。

但是因为Venn在这种做法上施加了魔法，所以复杂度是正确的。

其实我们上述复杂度的分析，给出的复杂度上界达不到，我们考虑并不是他的时间复杂度。我们换一种分析方式，对于选择的每一个度数小于的点，他向外会扩展最多次。对于度数大于的点，他会向外扩展多次，但是由于所有点的度数之和不能超过2倍的,所以单次均摊是次扩展，这样的点不会超过个，因为所有点的度数之和等于。那么总时间复杂度就为