recollector

$f_{i,j}$ 表示 $i$ 的子树中重链高度为 $j$ 的概率，转移的时候首先合并出 $F=\prod_{j\in son_i} f_j$，然后对于每个儿子暴力计算多项式除法，暴力枚举该儿子的重链长度和其他儿子的重链长度和转移。

时间复杂度 $O(n^2)$。

string

用状态 $(i,j,k,0/1)$ 表示当前串匹配模式串 $s$ 的长度，当前比 $s$ 小的子串数量，严格比 $s$ 小的前缀数量，和是否已经包含 $s$ 作为子串。转移的时候枚举下一个填的字符，在 kmp 上预处理之后就可以 $O(1)$ 转移。

显然 $j\geq \binom{k}{2}$，所以 $k$ 只会转移到 $O(\sqrt m)$ 级别。时间复杂度 $O(nm^{1.5})$。

night

再说。

perm

首先二分出 $0$ 的位置，然后询问所有包含 $0$ 的前后缀的答案。然后考虑 checker 的写法，不断找到两边 mex 增加的地方中 mex 较小的那个，可得到上一次的 mex 到当前的 mex 的数在某个区间中。这些限制是充要的，构造方案很简单。

把二分改成不断询问某个后缀直到答案是 $0$，这些询问的后缀（除了最后一个）都是在之后要用到的，所以可以把询问次数优化到 $n$ 次。

starmap

按照 $k\bmod 4$ 可以分别得到度数的奇偶性是否固定以及边数的奇偶性是否固定四种情况，容易求出最后的图要长成什么样子，然后将问题转化为所有点度数都是偶数，且边数是偶数的情况。

注意到对 $\{a,b\},\{b,c\},\{c,d\},\{a,d\}$ 和任意一个大小为 $k-2$ 的子集进行操作，可以得到一个四元环。我们先用四元环把所有连通块连起来，然后求欧拉路径。欧拉路径的长度一定是偶数，且每次可以用四元环把三条连着的边缩成一条边，可以在 $n^2+O(n)$ 步内解决问题。

在开始判断前对整张图进行 $O(n^2/k^2)$ 次随机操作可以把图几乎打乱成随机的，会大大减少操作次数，可以直接通过。或者可以通过每次处理一个点，直到 $n=k+2$，然后对 $\binom{k+2}{2}$ 次最终操作去重，得到严格 $\binom{n}{2}$ 的步数。

industry

首先对所有子树和子树补按照高度排序，用线段树哈希容易在 $O(n\log^2 n)$ 的时间复杂度内求出所有子树和子树补的排名。用直径中心作为树根可以只用求所有子树的排名（因为此时所有子树补的高度都高于所有子树），可以把这一部分优化成 $O(n\log n)$ 甚至线性，但没啥用。

对于 $o_x+o_y=1$ 的部分分，可以分别得到两边的单调性，主席树配合二分可以做到 $O(\log n)$ 单次询问。

写一个树上莫队即可通过，时间复杂度 $O(n^{1.5}\log n)$。单根号的做法再说。