先考虑 $O(nq)$ 做法。枚举每个点为根去 DFS 做 dp。

不难发现两个相邻的点不能操作二，所以状态要设 $f_{i,2}$ 表示点 $i$ 操作二，把子树的边覆盖完的最小操作。

若一个点不进行操作二，则他到子节点需要用操作一来覆盖，而一个操作一可能端点在两个儿子。考虑先把这个操作一的链拆开，然后从儿子向上合并时去匹配。设 $f_{i,1},f_{i,0}$ 表示点 $i$ 进行操作二，覆盖后子树内留下一个到儿子的操作一半条链没有匹配或全部匹配完。

然后考虑 dp 转移，分类讨论即可：

$$f'_{x,0}\gets \min(f_{x,0}+f_{y,2},f_{x,1}+f_{y,0},f_{x,1}+f_{y,1}-1)$$

$$f'_{x,1}\gets \min(f_{x,1}+f_{y,2},f_{x,0}+f_{y,1},f_{x,0}+f_{y,0}+1)$$

$$f'_{x,2}\gets f_{x,2}+\min(f_{y,0},f_{y,1})$$

然后直接转移就可以，复杂度为 $O(nq)$。

考虑换根出答案？但是这个贡献形式比较难拆开，考虑用矩阵描述 dp 的转移，这样做前缀后缀的转移就转化为求矩阵前缀后缀积了，本来矩阵乘法需要严格控制顺序，但这个东西先合并那个子节点无所谓，所以瞎做就行。

复杂度为 $O(nV^3)$，其中 $V=3$。

先拓扑排序建立一棵有根树。对于每个节点，存一个区间表示取值这段区间内答案最优。然后每次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)$。

先考虑一下朴素的 dp。

不难发现，对于一个集合最重要的是集合里最小的元素，剩下的元素对应的 $a_i$ 都大于这个值，可以考虑把所有值按照从大到小排序，则集合里其他元素都在最小元素之前。

对于第 $i$ 个数，考虑这个数是集合里最小的元素，或不是最小的元素对应的方案数。 $dp_{i,j}$ 表示 $1\sim i-1$ 个数处理完后，还剩下 $j$ 个数未确定属于哪个集合的方案数。

若第 $i$ 个数不是集合里最小的元素：

$$dp_{i+1,j+1}\gets dp_{i,j}$$

若第 $i$ 个数是集合里最小的元素，枚举这个集合里还有几个元素，即：

$$dp_{i+1,j-k}\gets dp_{i,j}\times \text{C}_j^k(0\le k<a_i)$$

初始状态为 $dp_{1,0}=dp_{1,1}=1$，目标状态为 $dp_{n+1,0}$。转移的过程中对于第二类转移需要枚举 $k$，复杂度为 $O(n^3)$。

考虑如何优化这个 dp 的第二类转移，将组合数拆开得到：

$$dp_{i+1,j-k}\gets dp_{i,j}\times \frac{j!}{k!(j-k)!}$$

假定对于阶段 $i$，设有

$$F(x)=\sum_{i>0}dp_{i,j}j!x^j$$

$$G(x)=\sum_{i>0}\frac{1}{k!}x^j$$

实际上是将 $F,G$ 做一个减法卷积的到 $H$，则有

$$H(x)=\sum_{i>0}dp_{i+1,j}j!x^j$$

对于减法卷积，可以翻转一个多项式的次数，此时减法卷积就转化成了加法卷积，直接用 NTT 计算即可。

可以选择为 $dp_{i,j}$，也可以直接维护 $dp_{i,j}\times j!$。算法的复杂度为 $O(n^2\log n)$。