A
已知一个字符串 \(n\le 1e3\) 中的若干信息，：\((x,y,z)\) 表示 \(x\) 后缀和 \(y\) 后缀的 \(\text{LCP}=z\).
求满足条件的字典序最小的字符串。
已知 \(a_{x+i}=a_{y+i}(i<z)\)，考虑维护并查集，一定相同的在一个集合。
然后要处理的是 \(a_{x+z}\neq a_{y+z}\)。从前往后填即可。
B
一个网格图满足 \(nm\le 5e4\)，有若干格子不能通行。有 \(k\le 100\) 个单向的传送门。
每次询问一个点能否到达另一个点。
先缩强连通分量，然后由于 \(k\) 比较小，直接 dfs 即可。
C
\(n=1e6\)，有 \(A,B\) 两个整数序列（有负数），每次给定 \(p,k\) 询问包括 \(p\) 的所有区间中 \(\max(\sum a-k\sum b)\)。
离线询问，每个询问就是找到 \(p\) 之前和 \(p\) 之后的前缀与后缀最小值减去。
发现这是一个一次函数的形式，直接李超线段树即可。
D
一棵树（\(n\le 8000\)），询问所有大小是 \(n\) 的有标号无根数中恰有 \(k\) 条边与原树相同的方案数。
Cayley公式：一个完全图有\(n^{n-2}\)棵无根生成树，经典问题prufer序列证明
扩展Cayley公式：被确定边分为大小为\(a_1,a_2,\cdots, a_m\)的连通块，则有\(n^{m-2}\prod {a_i}\)种生成树
证明就不再赘述了
那么我们可以通过 强制一条边出现或者是不出现 来统计边数
通过扩展Cayley公式统计强制的边能够得到多少树
比较Naive的想法，我们可以直接在dp中记录连通块大小、相同边数
每次断开一个连通块，乘上一个\(n\)的系数
强制相同的边，直接合并两个连通块即可
\(dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i+k,j+l+1}\)
强制不同的边，用不合并的-合并的即可得到
\(nk\cdot dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i,j+l}\)
\(-dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i+k,j+l}\)
优化的话首先优化连通块大小，可以通过一个经典的转化：
\(size\)作为系数，转化为在这个连通块中选出一个关键点（很显然\(size\)多大，就有多少中选出一个关键点的方案）
这样这一位被压缩到\(0,1\)，只需要记录是否在这个连通块中选择了关键点
这样复杂度等同于经典树形背包问题，但是空间略紧张
可以将第3维用拉格朗日插值换掉
设答案数列为\(a_i\)，转化为多项式\(A(x)=\sum_{i=0} a_ix^i\)
带入\(x_0=0,1,\cdots ,n\)，求得\(A(x_0)\)的数值，然后插值得到多项式
这样第三维就合并可以直接用\(x_0^k\)换掉