A.小蒟和他的乐谱

签到题，将原序列对取模之后将序列扫描一遍就可以得到答案。

B.小琛和他的学校

树是无根的，可以随便选取一个校区作为根节点。不妨设1号校区为根。

对于每一个校区，可以通过DFS计算出它子树中校区的个数以及子树中学生的总数。

然后再次进行DFS，假设son为当前遍历到的节点的某一个子节点，那么连接它们的这条边所需支付的维护费用为。

时间复杂度为。

C.小魂和他的数列

由于比较小，所以可以先将原序列离散。

之后通过棵树状数组分别维护1元、2元、3元...K元的单调上升子序列的个数。

时间复杂度为。

D.小翔和泰拉瑞亚

首先可以枚举一个位置，尽量使它的高度降低，用掉所有包含该位置的魔法，然后求出全局的最高位置，用最高位置与当前枚举到的位置的高度差来更新答案。这样必定能够求到最优解。

所以可以从左到右枚举位置，当当前枚举到的位置进入某一个魔法的区间时，就应用它。出来的时候就撤销它，然后通过线段树来维护最大值。

判断进入某一个魔法的实施区间可以按照左端点排序，实施了之后扔进按照右端点为关键字的小根堆里判断是否出了区间即可。

时间复杂度。

E.小雀和他的王国

当图中的割边被断开之后，原图就会不连通。所以要尽量让割边的数量减少。

可以先随便求出原图的一棵生成树。

然后通过树上差分或者Tarjan算法求出割边。

新连一条边之后，在生成树上新连边的两端点之间的路径上的割边将不再是割边，所以需要求出一条割边最长的路径，就是求一棵树的带权直径，DFS或者树形DP求出即可。

F.小球和新型材料

先考虑如何求出字符串在每次循环移动过后回文子串的个数。

先把字符串复制一次接在后面。

然后我们要求的就是区间这个区间内的回文子串个数分别有多少个。

可以用马拉车算法求出以每个位置为中心最长的回文串长度。然后考虑对这个区间的贡献。

先考虑回文长度为奇数的情况：

设当前回文中心的位置为，以为中心的最长的回文串的左端点为，右端点为。那么它对第个区间到第个区间都有的贡献。

对于第个区间和第，贡献为；

对于第个区间和第，贡献为；

以此类推，直到贡献为（假设这些区间都存在的话）。

相当于按位加上一个等差数列，线段树维护即可。回文长度为偶数也同理。注意细节即可。

然后就可以判断出回文子串个数之差是否大于了。

再来考虑如何求最大收益。

把式子用二项式定理展开，就是：

由于比较小，可以分P次求和，然后再累加起来。

考虑如何求：

把倒过来，就是：

这就是一个卷积的形式，所以只要把B复制一遍，分别求出A在次方和B在次方后的值，然后用NTT把两个式子卷乘起来，最后乘以并累加，就能得到每次循环移动后的收益。最后减去乘以移动次数后取最大值即可。

时间复杂度。