先拓扑排序建立一棵有根树。对于每个节点，存一个区间表示取值这段区间内答案最优。然后每次sort儿子中限制后合并即可。时间复杂度O(nlogn)

原题:bzoj4297

先考虑k≤8，字典序类问题使用逐位确定。状态为使用过的几种字符分别使用了多少次，状态数≤(k +1)!。预处理时需要再记录前一个使用的是哪个字符。

当k>8时，每次输出一串形如ababab...baba的前缀，可以把k减小2。

果然字符串的终点和字符串没什么关系吗。

不难发现我们每次只会在一个长竹竿后面拼接一个基础的短竹竿来增加长度。假设每次拼接竹竿的重叠部分为 $p$，显然 $p$ 是字符串的一个 border。

我们可以把这个字符串的所有 border 求出来，得到一个大小为 $m$ 的集合 $\{b_i\}$。最后要求的就是满足 $v\in [0,w-n]$，且方程 $\sum_{i=1}^m b_ix_i=v$ 存在解的 $v$ 的数量。

好的，后面是一个经典的同余最短路问题，于是我们得到了一个 $\min{b_i}\times n$ 的解法，但是这个做法是 $O(n^2)$ 的。

考虑优化这个做法，经典结论是一个字符串的 border 可以划分成 $\log n$ 段等差数列 $d_i+c_il_i$（结论证明较为复杂）。考虑对于每一个 $i$，求出在 $\bmod d_i$ 意义下，加入前 $i$ 个等差数列对应的边后的最短路。

依次加入每个等差数列，计算对最短路的影响。先考虑将原来 $\bmod d_{i-1}$ 意义下的最短路换成 $\bmod d_i$ 意义下的最短路，设前后两者对应的最短路数组为 $f_i,g_i$，可以用 $f_i+kd_{i-1}$ 去更新 $g_{(i+kd_{i-1})\bmod d_i}$，其中 $k$ 是没有限制的。

可以看成每个点 $i$ 向 $(i+d_{i-1})\bmod d_i$ 连一条有向边，这样整个图显然会划分成 $\gcd(d_{i-1},d_i)$ 个环，每个环之间独立。这样就很好做了，断环成链复制一遍，然后用环上上一个位置更新当前位置，总复杂度 $O(n)$。

转化完模数后，考虑用 $g_{i}+kc_i$ 去更新 $g_{(i+kc)\bmod d_i}$，其中 $k\in [0,l]$，还是可以看成每个点 $i$ 向 $(i+c)\bmod d_i$ 连一条有向边，划分成 $\gcd(d_i,c)$ 个环，但只能转移一次，最多从前 $l$ 个位置转移，单调队列 $O(n)$ 即可。

这样时间复杂度为 $O(Tn\log n)$。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19373303

此题目前无 spj，遂 30 pts.

大意

$m$ 对关系 $(u, v)$，第 $i$ 对表示 $i$ 这个点可以选择 $u$ 或 $v$。求最大的选择题数的方案数和方案。

（如果一道题做不出来就无法进行下一道题目）

思路

考虑二分图最大匹配。

实则并不算最大匹配，我们通过读题可以发现其实就是二分图匹配的过程，每次找一条增广路，如果找不到了，就说明当前无法继续进行这个游戏了。

也就是在匹配的过程中记录答案，如果找不到增广路径，那就直接 break 即可。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19359545

考虑树上背包。

定义状态 $f_{u, j}$ 表示 $u$ 节点，切掉 $j$ 个所需的最小花费。

那么我们的初始状态就是 $f_{u, 0} = 0$, $f_{u, sz_u} = 1$。

然后我们考虑如何进行转移：

$f_{u, j} = \min(f_{u, j}, f_{u, j - k} + f_{v, k})$

然后考虑我们的答案如何进行计算，显然是 $f_{u, sz_u - p} + f_{u, sz_u}$，这个地方的 $f_{u, sz_u}$ 的值显然是 $1$，但是只有根节点是 $0$。

这个地方实际上就是为了让你的选出来的这 $p$ 个点与你原来的 $u$ 子树脱离，显然需要你删一条父边。