[NOI2015] 品酒大会
若建出后缀树，我们可以发现，产生贡献的是每个点对。考虑在其最近公共祖先处统计答案。
因此对于每个点，我们需要统计其子树中每个权值的最大值和最小值，以及子树大小即可解出答案。
使用后缀自动机建出后缀树，然后统计即可。
[AHOI2013] 差异
将题目中的算式放到后缀树中考虑，发现其实就是求后缀树中每个点对的带权距离。
考虑计算每条边的贡献，即每条边的权值乘上其两端点的子树大小之积。
【模板】广义后缀自动机（广义 SAM）
将所有字符串插入字典树，然后按字典树的拓扑序依次将节点插入后缀自动机中即可。
诸神眷顾的幻想乡
发现树链上的字符串一定为从某个叶子出发得到的所有字符串中的子串。
因此我们可以将从所有叶子节点出发得到的所有字符串插入广义后缀自动机中，然后求出本质不同子串个数即可。
[CTSC2012] 熟悉的文章
发现答案具有单调性，因此可以二分答案，下面考虑如何判定答案。
判定的主要任务是求出一种划分方式，使得被匹配的长度和最大。不妨设 \(f_i\) 代表文本串前缀 \(s_{1 \dots i}\) 通过某种划分方式被匹配的最大长度。
那么通过枚举上一次划分的位置，我们可以得到状态转移方程：
\[f_i = \max\left\{f_{i - 1}, \max_{j < i - L} \{f_j + i - j\}\right\}
\]
上式中 \(L\) 代表判定的答案，同时我们发现上述式子中对 \(j\) 的限制是不完全的，因为我们还需要限制 \(s_{j + 1, i}\) 在模式串中出现。设 \(l_i\) 代表文本串前缀 \(s_{1 \dots i}\) 最长的在模式串中出现的后缀的长度，该值可以通过对模式串建出广义后缀自动机后对文本串进行匹配得出。那么合法的 \(j\) 应该满足 \(j \in \left[i - l_i, i - L\right]\)
由于该区间的左右端点均是单调的，因此可以使用单调队列优化转移。
复杂度为 \(O(n \log n)\)，其中 \(n\) 为文本串长度。