A-梦想赛道

不难发现有一种最优的方法是在两个有边的点对之间加一条权值为的方法，所以答案就是树的所有边权和。注意因为所有边权都要求是正整数所以如果树的边权全是就要输出-1 。

B-寒冬信使

因为每次抵消两个棋子，所以无论如何操作，减去的次数都是偶数，所以次数的奇偶性都是固定的。

直接判断操作次数的奇偶性即可。

时间复杂度：

C-盾与战锤

首先每次必定是能够把盾破开的，否则这些攻击没有意义。

假设盾被破开 次，那么就能够抵抗 点伤害，我们可以使用 次攻击，由于抵御的伤害确定，所以我们肯定是选择最大的那些。

所以按照伤害排序，然后对于每个 枚举破开多少次盾就好了。

时间复杂度：

D-妄想集合

考虑一个最大的集合无法组成三角形，那么这个集合中的元素为 。

不难发现这就是斐波那契数列，然后到 以内的最多才只有四十多个数，所以如果一个区间元素个数大于一个上限 就直接输出YES，修改时也只需要修改元素个数少于的集合即可。

我们用并查集维护一个位置下一个元素个数没有大于 的集合的上一个位置，然后一个一个跳即可。这样每个位置期望最多操作次数为 。

时间复杂度：

E-秘密构成

因为两个的贡献是分开来的，所以我们将这两个的贡献分开计算。

转移到 时 表示这一个的选择的二元组的 是 ，上一个选择的二元组的 的是 。

那么根据更改 ，那么之后的 表示下一个的选择的二元组的 是 ，这一个选择的二元组的 的是 。

那么转移 时方程为
$$

然后再转移 ，方程为

可以发现两个转移的复杂度时分开的，所以时间复杂度 。

F-延误列车

先考虑 时怎么做，我们可以用总的生成树个数减去包含这条边的树。

考虑怎么计算包含这条边的生成树个数，也就是原图分成以 和 为根的两棵树的方案。

可以视为若干棵有根树拼接起来，枚举第一棵树的大小

那么不合法的方案数就是 ，这样可以做完 了。

将上面的式子组合数拆开然后 卷积计算每个 的答案得到数组 。

然后当 时我们先用上面的方法计算包括至少一条边的情况，之后要加回包括两条边的情况。

这个的话我们相当于用上面的式子再卷一次

然后用 计算就好了。

实际上因为只需求一个 的所以可以暴力枚举没必要再卷一次。

然后 时我们可以沿用前面的思维，指定一些边必须选择然后容斥。

对于删除的边分成以下情况

• 一条边都不指定，那么方案就是

• 指定全部边，此时我们可以将 和 卷起来得到指定四个点已经连接了的答案。（当然由于只需要计算 位置的值所以可以直接枚举）

• 指定一条边且是最左右两边的边，此时和上述 时的计算方法相同

• 指定两条边，此时和上述 时的计算方法相同。

• 指定一条边且是在中间那条，此时树被分割成了两个部分，并且这两个部分需要连接。考虑构建一个连接这两个部分的方案的多项式。

  方便的是两个部分独立部分的多项式就是 。

  当有 个点在这两部分之间时方案应该为 （中间插入一棵树且选择两个点来连接这两个部分），也就是定义多项式 ，然后 计算 （还要乘 是因为中间连接的部分的方案 ） 。

时间复杂度：

然后被爆标了，具体的就等playf大爷的视频讲解了/kk