传送门题目描述给定一个长度为\(n\)的字符串\(S\)，令\(T_i\)表示它从第\(i\)个字符开始的后缀。求\[\displaystyle\sum_{1\leqslanti<j\leqslantn}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)\]其中，\(\text{len}(a)\)表示

后缀自动机维护子串公共后缀方便一点，所以直接倒序插入字符串即可。我们给所有前缀打上标记，然后跑树形\(dp\)，设\(sum_i\)表示第\(i\)个点的子树内有多少个前缀，\(ans\)统计\(\sum\text{LCP}(T_i,T_j)\)，则有：\[ans=\sum\limits_{i=1}^{id}\sum\limits_{j\inison}{sum}_j({