环球旅行

题意就是给出一棵带边权的树。删除上面的一条边，使分成的两棵树中较大的直径尽量小。求该直径。

【20分做法】

枚举删除哪条边，计算直径。复杂度

【30分做法】

对于菊花图，删除最长边即可。

【40分做法】

对于一条链，枚举删边，可以直接算出剩下两条链的直径。

【60分做法】

对于且数据随机的部分，答案肯定是删除直径上的某条边。随机数据树的直径不会很长，所以只枚举删除直径上的边。计算剩下的最长直径即可。

【100分做法】

将直径扯平。从左向右依次计算删除上面某条边后左边子树的直径。

如图，删除红色边之后，左边子树的直径就是max(删除蓝色边时的答案，经过x但不经过y的最长链+蓝色边长度+y子树中与y相连的最长链长度)。
用同样的方法从右往左依次计算删除某条边后右边子树的直径。然后就可以统计出删除每条边之后的代价。
我们直接分别以直径的两个端点为根，用树形dp的方法求出每棵子树的直径。最后统计一遍答案即可。

恢复数列

【30分做法】

爆搜

【50分做法】

出题人也不知道怎么写233，但是鉴于这是OI赛制，就留给选手发挥吧。

【100分做法】

首先有一个结论：原题有解的充要条件是。这个的证明放到后面。
题目保证有解，所以全部数据都是满足这个性质的。
设。
有一种可行的构造方法是让k。然后在中，取个为,个为,个为个为。
这样左侧就是
恰好等于右侧。
关于上方结论的证明：
对原式两边，得到一个必要条件为
即
再加上上方的构造方法，可以得出是原式有解的充要条件。

回到过去

个物品，想要权值和为。当哪些种类的物品不选时，一定不能使权值和为。

【20分做法】

爆搜。

【40分做法】

f[i][j][k]表示前i个物品权值和为j，不选择第k种，是否可行。转移即可。
复杂度

【60分做法】

对于每种时光胶囊只有一个的情况，表示前i个物品权值和为j是否可行。表示后个物品权值和为是否可行。枚举不选的种类。然后将数组和数组合并一下即可。

【100分做法】

注意到不同种类的胶囊权值之和不超过所以胶囊的种类不超过450种，然后用和上面类似的方法二进制优化分组背包dp一下。复杂度。仍然过不去。发现dp值只有0和1。Bitset优化一下即可。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43362152

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43362161

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43362163