前置知识：后缀树，后缀自动机
问题导入：有一个长度为5·105的字符串，对这个字符串建立后缀树，后缀树一条边的权值为这条边所代表的字符串中本质不同的子串个数，求这个后缀树边的权值和
来源：opentrains1464 Petrozavodsk Summer−2015. Moscow IPT Contest H.Sasha and swag strings
今天我们要介绍：压缩后缀自动机CSAM:compacted suffix automaton
网上关于压缩后缀自动机的资料极少，本文大部分来自作者思考的结果，发现了很多有意思的小性质。
后缀自动机的fail树
一个串后缀自动机的fail树是这个串反串的后缀树。
证明：在构造后缀自动机时，我们是插入他的前缀，并取right集合来合并子串，等价于其反串的后缀树
后缀自动机的后缀图以及其与后缀树的联系
后缀图即为后缀自动机中转移边组成的DAG，这个图与fail树不一样，后缀图蕴含了原串的后缀树
说明：从下文开始，为了引用方便我们会将性质进行编号
我们考虑后缀图，它显然有以下性质：
（1）.从空节点开始，在后缀图上可以得到的任意一条路径，都是原串的一个子串
我们来考虑原串的后缀树，后缀树是将所有后缀插入trie树得到的。但我们可以使用一个等价的描述：
(2).后缀树是将串的所有子串插入trie树得到的。
将(1)(2)性质进行对比，不难发现：在后缀树中，将一些完全相同的子树的根节点进行合并，就得到了后缀图。
接着我们可以得到如下性质：
(3).从空节点出发的任意两条不同的路径，所经过的字符拼接形成的字符串不同（今后我们将这个字符串直接称为“这条路径代表的字符串f(S)”）
这一点可以通过数学归纳法证明：考虑这两条不同路径首次分道扬镳的地方，一定是经过了不同的字母转移
(4).后缀树上每条从空节点开始的路径代表的字符串不同（trie树性质），且这些路径和后缀图中的那些路径是一一对应的。
对于性质(4).我们考虑刚才已经发现的，后缀图是由后缀树中相同的子树合并而成，这个性质就十分显然了。
(5).在后缀图上，对任意两点u,v,若存在两条路径S1,S2都是从u到v，那么f(S1)和f(S2)中必然一个是另一个的后缀。
证明：考虑从空节点到v的所有路径代表的字符串，他们交汇于v说明他们拥有同一个right集合，也就是说他们中每两个都是其中一个是另一个后缀的关系，那么f(S1),f(S2)从u到v，则是这些后缀中某个后缀的后缀，自然也满足一个是另一个后缀的关系。
压缩后缀自动机
严格来讲是压缩后缀图。
压缩的思路是怎么来的呢？
定义：对于后缀图中的点，若这个点出度为1称为坏点，否则称为好点
后缀路径：后缀图中一条开始于好点，终止于好点，中间经过的全是坏点的路径叫做后缀路径。
(6).极其重要的性质：后缀图中的每个后缀路径代表的字符串一定是后缀树中某条或某些边上的字符串。
证明：我们从空节点开始，在后缀图和后缀树上同时使用相同的字母转移来行走。
走到后缀树的某个节点时，这时走在后缀图上的位置必然是一个好点(否则只有一条出边，这会在后缀树上被缩起来)
走在后缀树的某条后缀边内部时，这时走在后缀图上的位置必然是一个坏点（否则多条出边在后缀树上无法合并）
这样结合性质(4)就证明了,每条后缀路径都对应了一些后缀树上的边。
使用上面的”树图同步行走思想”，我们发现走过某条后缀树边的过程一定是走过某条后缀路径的过程。这样的话，我们就可以给每一条后缀树边安排一个对应的后缀路径。这是一个一对多的映射，每条后缀路径可能对应多条后缀树边但一条后缀树边只对应一条后缀路径，但每条后缀路径和后缀树边都一定有对应对象（考虑同步行走的过程）
(7).一个后缀路径对应的后缀树边的条数，即为：从空节点经过后缀路径走到后缀路径终点的方案数。
证明：每一条从空节点经过后缀路径走到后缀路径终点的方案，在”树图同步行走”中都对应着一条从后缀树根走到某个后缀树边终点的过程，而在后缀树中，由于树的性质，不同的行走方案一定走向的是不同的终点，因此行走方案数等于对应的后缀树边的数量。
(8).对于一个后缀图中的节点，从空节点走到这个节点的路径数等于这个节点代表的子串的数量，即普通后缀自动机中的len[x]−len[link[x]]
证明：我们考虑，所有从空节点走到这个节点的路径代表的字符串都是这个节点代表的子串其中的一个，这些子串两两不同（长度都不相同），因此结论成立。
(9).由于一条后缀路径中间经过的都是坏点（一条出边），因此一个后缀路径对应的后缀树边的条数等于从空节点经过后缀路径走到后缀路径终点的方案数等于从空节点走到后缀路径起点的方案数
Swag Strings
现在我们可以回归那到题目，设uS,vS分别为路径S的起点和终点，设g(S)为字符串S包含的本质不同子串的数量，则答案即为：
ans=∑S∈后缀路径(len[uS]−len[link[uS]])g(f(S))我们枚举后缀路径计算即可。
(10).设原后缀图的边数m，则后缀路径数量小于等于m
证明：我们把后缀路径分为两类：
(a):一条边，起点终点都是好点，这类边的数量等于x=（起点终点都是好点的边的数量）
(b):后缀路径上经过坏点，我们考虑这条路径上的第一条边，这是一个起点为好点终点为坏点的边，由于坏点只有一个出边，那么实际上路径就没得选，只能一直往坏点唯一的出边走直到碰到好点。因此这类边的数量等于y=(起点好点终点坏点的边的数量)
显然x+y≤m
因此枚举后缀路径复杂度是没有问题的。
我们的压缩后缀图的意思便是：将所有出度为1的点的出边对应字符串合并进它的所有入边。然后删掉这个点。并将这个点的所有入边接进这个点的唯一出点。这样，新的压缩后缀图的每一条边都是一个原图的后缀路径
后缀路径数量复杂度没有问题，但计算g(f(S))可不能暴力计算，∑S∈后缀路径|f(S)|是平方级别的。
但是。。。。。。
还记得我们的性质(5)吗，它就是我们的杀手锏
我们考虑枚举vS,对vS相同的后缀路径在一起计算，由性质(5)可得，这些路径按照从短到长排序，短路径一定是长路径的后缀。
因此我们对每个vS找到其中长度最长的一个Smax,我们只需求出Smax的每个后缀的g值，就可以知道所有这一类后缀路径的g值。
这只需要对Smax的反串跑后缀自动机，就可以轻易统计出Smax每个后缀的g值
时间复杂度O(∑u∈压缩后缀图节点|压缩后缀图中以u为终点的边S中最长的f(S)|)
考虑压缩时每次将坏点删除的操作，实际上是将坏点唯一出边对应的字符串接到这个坏点唯一出点上，因此原后缀图上每一个字母最终最多只会作用于一个节点上、被容纳进以该点为终点的后缀路径中的最长的一个上来为复杂度做贡献，因此复杂度是小于O(m)的。
小总结：
trie树−压缩−>后缀树−最小化−>压缩后缀图
trie树−最小化−>后缀图−压缩−>压缩后缀图
最小化：即DFA最小化，通过类似同构点的合并的操作来简化图的转移，在这里，最小化指的就是将树的某些完全相同的子树的根节点合并
压缩：将出度为1的点删除，将它的唯一出边信息合并于入边信息，并将它的所有入边重定向到它的出点上。
关于本题其他的方法：
每条后缀树边相当于串中的一个子串，用反串的后缀自动机建出后缀树，便相当于询问串中n个子串的价值和。这在2018年国家集训队论文集中陈江伦的论文中被详细讨论，是使用LCT的某些高级技巧做到nlog2n,有空的话要学习一下。