LibreOJ 2377 「AHOI2013」差异

假设把原串放在后缀树上，LCP 即后缀树上的 LCA。
看看题目里这个式子，不觉得……很像树上路径长度？
所以可以对于每条边，算它的贡献。
DP 即可。

考虑一条边的贡献。
其实就是 lenp−lenfap，又是熟悉的式子。

然后要知道一个性质，后缀树相当于把原串翻转之后插进后缀自动机后的 Parent Tree。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 5e5;
int n,a[(N << 1) + 5],cnt[N + 5];
char s[N + 5];
struct node
{
    int ch[26];
    int fa,len;
} sam[(N << 1) + 5];
long long ans;
int sz[(N <<1) + 5];
int whole = 1,tot = 1;
void push(int x)
{
    int cur = whole,p = whole = ++tot;
    sam[p].len = sam[cur].len + 1,sz[p] = 1;
    for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
        sam[cur].ch[x] = p;
    if(!cur)
        sam[p].fa = 1;
    else
    {
        int q = sam[cur].ch[x];
        if(sam[cur].len + 1 == sam[q].len)
            sam[p].fa = q;
        else
        {
            int nxt = ++tot;
            sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
            for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                sam[cur].ch[x] = nxt;
        }
    }
}
int main()
{
    scanf("%s",s + 1),n = strlen(s + 1);
    for(register int i = n;i;--i)
        push(s[i] - 'a');
    for(register int i = 1;i <= tot;++i)
        ++cnt[sam[i].len];
    for(register int i = 1;i <= n;++i)
        cnt[i] += cnt[i - 1];
    for(register int i = tot;i;--i)
        a[cnt[sam[i].len]--] = i;
    for(register int i = tot;i;--i)
        ans += (long long)(sam[a[i]].len - sam[sam[a[i]].fa].len) * sz[a[i]] * (n - sz[a[i]]),sz[sam[a[i]].fa] += sz[a[i]];
    printf("%lld\n",ans);
}