题解
( exttt{SAM}) 做法，但此题并不是 ( exttt{SAM}) 模板题。
个人感觉洛谷上其他 ( exttt{SAM}) 的题解似乎都没有讲明白，或者是思考过程是错的（也可能是我理解错了）。
主要有以下几点问题（这里并没有讲清楚，会在接下来的题解中重新叙述一遍）：
- ( exttt{Parent}) 树上的节点深度并不是其串的长度。
- 我们统计的并不是任意两个节点之间的距离，而是 ( exttt{Parent}) 树上所有不是克隆节点之间的带权路径长度
- 对 ( exttt{SAM}) 的统计过程并不是直接对所有点对的统计，而是一种类似于边差分的思路。
接下来讲一下自己的理解。
以下不加证明地给出一些引理：
(Lemma(s))
- ( exttt{SAM}) 中最长链（终止链）上的所有节点的最长串，是原串的所有前缀
如：( exttt{aababa}) 的最长链上的节点表示的最长串分别是 ( exttt{a,aa,aba,aaba,aabab,aababa})
- ( exttt{Parent}) 树上两点的 ( exttt{LCA}) 所表示的最长串，是两点分别所表示的字符串的 ( exttt{LCP})
由引理一，我们考虑在 ( exttt{Parent}) 树上搞事情。
题目问的是所有后缀，那么建出反串的 后，由引理一可以知道，现在所有最长链上的节点的最长串，是原串的所有后缀，而且结合引理二有：此时 ( exttt{Parent}) 树上两点的 ( exttt{LCA}) 所表示的最长串，则变为了两点分别所表示的字符串的 ( exttt{LCP})。
那么我们现在在 ( exttt{Parent}) 树上进行统计，由于我们统计的是原串的一系列后缀，它们现在分布在 ( exttt{SAM}) 上最长链的节点中，那么我们就应该对最长链的节点点对进行统计（这也是答案式子中 sz[u]*(n-sz[u]) 的原因，因为原串的长度（最长链的长度）即为 (n) ， 而 sz[u] 表示的是当前节点的子树内原串的节点个数，那么 sz[u]*(n-sz[u]) 就是 ( exttt{Parent}) 中经过当前边的出现在最长链上的点对数量）。
考虑进行边差分：将 ( exttt{Parent}) 树上以节点 (u) 为儿子的边的权值赋为 maxlen[u]-maxlen[fa[u]]（请注意，这篇题解中，这个式子并不是用来表示某个节点的串的个数）。
那么现在对于任意两个终止链上的节点 (u,v) ，它们在 ( exttt{Parent}) 树上的 ( exttt{LCA}) 是 (w)，我们统计出所有这样的点对的 maxlen[u]+maxlen[v]-2*maxlen[w] 即为答案。（因为 maxlen[u],maxlen[v] 现在是原串的以两个后缀的长度，maxlen[w]是它们 的长度，这就是题目的式子）
最后将每条边的权值乘上经过其的点对数量即可，也即：
(sumlimits_{u in sam}(maxlen_u-maxlen_{fa_u}) imes size_u imes (n-size_u))
为什么呢？
我们考虑将一条以 (u) 为底的链统计完的过程，其中计算出来的是 maxlen[u]-maxlen[fa[u]]+maxlen[fa[u]]-maxlen[fa[fa[u]]]+...-maxlen[w]，那么对于 (u) 和 (v)，它们统计出来的答案便是maxlen[u]+maxlen[v]-2*maxlen[w]
那么这道题就做完了
代码里面的 link 其实就是 fa