CSP-S 前要多做树上问题 （主要是因为去年 NOIP D1T3、D2T1、D2T3 全是树上问题，然后爆炸了） 。

这题一看就是树形DP，状态也是一眼就能想到的。

令 $f_{i,j}$ 表示 $i$ 这个点染成 $j$ 的方案数，枚举 $son_i$ 的颜色来转移。

最后答案即为 $\sum_{i=1}^{m}f_{1,i}$。

首先我们要知道这道题的原型是「NOI2014」起床困难综合症。

总是有出题人喜欢把序列上用线段树解决的题目出到树上，让选手强行写个树链剖分或树分治或某种动态树数据结构。

序列问题转化为树上问题，很容易想到树链剖分，直接上板子。

我们通过观察可以发现 $11\cdots1$ 可以变化为 $\frac{10^{n}-1}{9}$，于是根据取模的性质，我们可以把原式两边同乘九再加一，原式变为 $10^{n} \equiv k \cdot 9 + 1 \pmod m$，发现这是个 BSGS 的标准式子，由于 $m$ 保证为质数，所以也不必用拓展 BSGS。

这道题第一眼像是合并果子，我们考虑贪心。

我们先选择一种贪心策略：每次选当前最大的两个数合并，直到只剩最后一件物品。

接下来我们证明一下为什么这样是对的：

我们先想一想合并果子，那道题的贪心策略与这道题相反，每次选最小的两个数合并。考虑它为什么是对的——我们发现越先选的数对结果的贡献越大，为了使结果尽可能小，肯定是越小的先选越好。

作为一道英文题，我们先解释一下题意：

给你一个长度为 $n$ 的 01 串，其中可能至少有 $t_{i}$ 个 1，问最后你给出一个 01 串可能和其匹配的最大长度。

接下来我们进入正题。

第一眼看见觉得是水题，对于每个 $t_{i}$ 枚举应该全 0 还是全 1，但是这显然可以找出反例来。

由题意得一个点对的联合权值是它们的点权相乘，而 2 个点形成点对的条件是距离为 2。

于是我们可以通过枚举这 2 个节点的公共点来算出以这个点为中心的权值和。

但是先枚举中心点再枚举其相邻的节点时间复杂度达到了 $O(n^3)$，我们不能承受。

经过观察发现，对于特定的点，它都要乘上除自己以外的所有点权，再相加。然后我们就可以先处理出点权和，统计答案的时候把自己减去即可。

很容易看出这是宽度优先搜索，因为要求步数最少，且每个操作代价相同。

我们可以按操作类别分 6 种情况扩展，如果搜到最终状态就跳出 BFS（搜索顺序可以随意，因为 spj 已经配置好了，不像数据修改前要有特定的顺序）。

记得标记已经出现过的情况，不然会 TLE/MLE；

根据题意我们发现对于每个 $A_{i}$ ，与它绝对值最小的一定是前 $i$ 个数排序后在它前面或后面的数。

这样的话，我们维护一个单调的序列，插入每天的营业额时计算其波动值即可。

最暴力的便是插入排序，复杂度 $(N^2)$，不能忍受。。

我们应选择复杂度为 $(NlogN)$ 的方法。

维护一个单调序列自然想到了 set（平衡树也可以，但是作者想用 STL 水过去，雾），因为可能有多个相同的营业额，所以选择了 multiset。

我们根据题意，发现这是一个 DP 题，定义$f_{i,j}$表示在高度为$i$，当前要爬的树为$j$所能获得的最大柿子数。

易得状态转移方程：$f_{i,j}=max(f_{i-1,j},f_{i-delta,k}) (1\leq k \leq n)$，当$i>delta$时后一项成立。

于是我们得到了一个时间复杂度为$O(H \times N^2)$，空间复杂度为$O(N \times H)$的算法啦。。