【BZOJ1921】【CTSC2010】珠宝商（点分治，后缀自动机）

题面

BZOJ权限题

题解

如果要我们做暴力，显然可以以某个点为根节点，然后把子树\(dfs\)一遍，建出特征串的\(SAM\)，就可以直接计算出现次数了。复杂度是\(O(size^2)\)

另外一种暴力是我们枚举以某个点为中心，考虑在其两棵不同子树内各选择一条链，然后拼接在一起计算答案。我们假设选择了\(R\)为中心，然后有一条\((u\rightarrow R)\)的链，有一条\((R\rightarrow v)\)的链，我们把\((u\rightarrow R)\)这个串在每个匹配到的结尾位置打上一个标记，把\((R\rightarrow v)\)这个串在每个被匹配到的开头位置打上一个标记，于是我们就只需要把每个位置的左右两个标记乘起来就是答案了。

然后考虑怎么打这个标记，对于在开头位置打标记，显然是匹配上了一个后缀的前缀，那么我们把后缀树建出来，因为每一个后缀上的一个叶子节点对应着一个后缀，这样子我们只要在后缀树上找到这个串匹配的节点，然后其子树的所有叶子节点对应的后缀的开头位置都要\(+1\)，于是子树加可以变成在后缀树上的匹配点单点加，最后一次\(dfs\)一次后缀树就好了。类似的，在结尾位置打标记就是在前缀的一段后缀打标记，那么建出前缀树就行了。于是我们就可以做到\(O(m+size)\)，其中\(m\)是特征串的长度。但是这样子会出现\(R\)的相同子树里的一个从上往下的串和一个从下往上的串进行了匹配，于是我们还要对于每一个子树进行去除。

现在有了这两种复杂度不同的做法，显然我们可以按照\(B=\sqrt m\)来分类讨论，对于\(size\le B\)直接\(O(size^2)\)暴力，否则对应下面这种的\(O(m+size)\)的做法，注意对于容斥减去相同子树内的贡献的时候，也需要考虑使用两种对应的方法，否则复杂度是假的。

upd:

补一下关于复杂度的证明：

对于第一类暴力，单次是\(O(size^2)\)的，因为这样处理完之后所有子树的答案已经贡献完毕，可以直接返回，所以只需要在分治子树大小第一次小于\(B\)的时候统计答案，然后因为所有这样的子树两两不交，所以\(\sum size\)是不会超过\(n\)的，而\(\sum size^2\le \frac{n}{B}B^2=nB\)，所以这一部分的复杂度是\(O(nB)\)的。

对于第二类暴力，我们考虑\(size\gt B\)的分治重心的个数，根据点分治的性质，没有子树的\(size\)会大于父亲的一半，所以每次向上至少要合并两个\(size\gt B\)的分治子树，而这样子的子树不会超过$ \frac{n}{B}\(个，所以向上合并的次数不会超过\)\frac{n}{B}$次，所以这样子的分治重心的个数不会超过\(2\frac{n}{B}\)，而这样子单次复杂度是\(O(size+m)\)，所以这部分的总复杂度是\(O(\frac{n}{B}m)\)。

综上\(\frac{n}{B}m=nB\)，即\(B=\sqrt m\)的时候复杂度最优，为\(O((n+m)\sqrt m)\)。

---

代码被我咕咕咕了怎么办......