主题

主题

 
   

3238: [Ahoi2013]差异

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3238

Description


Input

一行,一个字符串S

Output

一行,一个整数,表示所求值

Sample Input

cacao

Sample Output

54

HINT

2<=N<=500000,S由小写英文字母组成


个人解法:

首先sigma(Tj)+sigma(Tj)可以预处理。

然后sigma(lcp(Ti,Tj))可以考虑使用后缀树。在后缀树上DP即可。

我们拿SAM建立这棵后缀树,需要求出size[x](x与Fa[x]这条边的边权),顺便求出maxn[x](root到x的边权和),树上DP即可。

枚举每一个子树,计算贡献,由于计算了两次可能需要考虑去重。如果当前子树的根也是一个后缀的话,要计算其和子树个点的贡献。


代码如下:

https://code.csdn.net/snippets/2279268

 
 
评论