241112

C. 逃跑

D. 树上最多不相交路径

维护一个大根堆，堆中元素的权值就是i到根节点的距离，然后不断弹出堆顶直到堆顶元素的权值小于l就行了

A 传送门

硬搜索

B 硬币游戏

考虑将$a,b,a$分成两组，$a,b$和$a$这样再使用桶排序就可以贪心了

C 序列计数

设 $f_i$ 表示以 $i$ 结尾 且之前没出现过 的子序列个数，$lasv$ 表示 $v$ 上一次出现的位置，则
$$f_i=\sum _{j=lasv}^i{f}_j$$

前缀和优化即可 $O(n)$ 完成。

$fi,j$ 表示前 $i$ 个数构成的以 $j$ 结尾的本质不同子序列个数，转移为
$$f_{i,j}=\{\begin{array}{c}{f}_{i-1,j},s_i\ne j\\ {\sum }_k{f}_{i-1,k}+1,s_i=j\end{array}$$

fi,j={fi−1,j,si≠j∑kfi−1,k+1,si=jfi,j={fi−1,j,si≠j∑kfi−1,k+1,si=j

直接转移的复杂度为 $O(n|\sigma |)$，矩阵实现为 $O(n|\sigma |3)$，显然对一般情况矩阵反而会造成负优化。

对于一些特殊的情况，例如转移矩阵周期性变化，就可以用矩阵加速。