归纳

树上莫队首先有一道题 王室联邦题目大意给定一棵树，将树分为大小范围为 $[B, 3B]$ 的连通块集，求方案 树上分块方法之一类似贪心，用栈维护还没有在连通块中的子节点，对于递归到的当前的点 $p$ ，扫描它的子树，能拼凑就拼凑 但是注意最后可能还会有一些点（一定包括根）剩下，那么将这些点并到最后一个连通块即可 显然每个连通块都满足大小为 $[B, 3B]$ 核心代码123456789101112131415void DFS (int root, int father) { int bot = top; for (int i = Head[root]; i; i = Link[i].next) { int v = Link[i].to; if (v == father) continue; DFS (v, root); if (top - bot >= B) { capt[++ bind] = root; while ...

后缀数组在文本串中寻找子串在文本串 $T$ 中寻找模式串 $S$，那么 $S$ 一定是 $T$ 的某个后缀的前缀，后缀排序后，在 $SA$ 中二分 $S$ 的位置，每次 $check$ 比较时间 $O (|S|)$，总时间复杂度 $O (|S| \log |T|)$ 比较两个子串的大小关系比较 $S$ 的子串 $A = S[l_1…r_1], B = S[l_2…r_2]$ 的大小关系 若 $lcp (l_1, l_2) \ge \min (|A|, |B|)$，则 $A < B \Longleftrightarrow |A| < |B|$，反之 $A < B \Longleftrightarrow rk_{l_1} < rk_{l_2}$ 本质不同子串数目设字符串 $S$ 长度为 $n$ $ans = \frac{n(n + 1)}2 - \sum\limits_{i = 2}^n height[i]$ 从字符串首或尾取字符构成最小字典序的字符串[USACO07DEC]Best Cow Line G 最基本贪心，若两端字符不同，优先取大的，那么问题就在于两端相 ...

对于 $n$ 个点组成的环大小为 $m$ 的基环树个数的问题，目前已知三种解法 解法一「动态规划」在环上每个点下面搭树的方案数，相当于是在完全图中制造生成树，然后提一个点（即环上那个点）为根，故可用 $n^{n - 2}$ 来计算 然后就可以很容易想到一种背包解法，把环随便找个地方断一下，把它看成序列，即可令 $f_{i, j}$ 表示环序列前 $i$ 个点，已经使用了 $j$ 个点做环下的树的方案数，显然$$f_{i, j} = \sum\limits_{k = 0}^j f_{i - 1, j - k} \times \dbinom{n - m - (j - k)}{k} \cdot (k + 1)^{k - 1}$$然后答案要对环进行圆排列，即 $ans = f_{m, n - m} \times \frac{A_n^m}{2m}$ 复杂度 $O (n^3)$ 当然这样复杂度比较高，可以考虑将已经拼好的连通块和已经拼好的一棵树连接起来，令 $f_n$ 表示 $n$ 个点的答案 当然，为了保证不会算重，需要有一个特征点，即保证点 $1$ 不会在环上，即$$f_n = \frac{n ...