Menci

「BZOJ 1396」识别子串 - SAM + 线段树

对于一个字符串 $S$，和 $S$ 中的第 $i$ 个字符 $x$，定义子串 $T = S(i \ldots j)$ 为一个关于 $x$ 的识别子串，当且仅当：

1. $i \leq x \leq j$；
2. $T$ 在 $S$ 中只出现一次。

求 $S$ 关于每一位字符的最短识别子串长度。

「SDOI2016」游戏 - 树链剖分

Alice 和 Bob 在玩一个游戏。
游戏在一棵有 $n$ 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 $123456789123456789$。
有时，Alice 会选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$，若 $r$ 与 $s$ 的距离是 $dis$，那么 Alice 在点 $r$ 上添加的数字是 $a \times dis + b$。
有时，Bob 会选择一条从 $s$ 到 $t$ 的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。
Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。