1. 题目

传送门=￣ω￣=

2. 题解

可以看出如果我们能建出后缀树就很简单了，只要在树上 lca 处数点就行了

然后我就去学了 Ukkonen，然而发现还不如老老实实用后缀自动机来得方便一些。

后缀自动机的 fail 树（也有人称之为 pre 树、next 树等等等等反正就是适配了跳转的边形成的那个树）其实就是原串的反串（翻转）的后缀树

所以我们只要把字符串倒过来插入，然后得到原串的后缀树再 Dp 一下就行了。

注意特殊处理 “儿子与父亲” 这对关系，因为 “儿子与另一个儿子” 会被统计两次，而 “儿子与父亲” 只会被统计一次，要手动乘二。

实际上字符串不倒过来插入也是可以的，因为 “各个后缀的最长公共前缀长度之和” 是等于 “各个前缀的最长后缀长度之和” 的。。。

感觉字符串好绕啊。。。还是贴代码跑路算了。。。

#include <bits/stdc++.h>

#define NS (1000005)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n;

char str[NS];

LL ans;

struct N
{
    int nxt[26], fa, mxl, sz;
    int& operator [] (const char c) {return nxt[c - 'a'];}
} e[NS];

struct SAM
{
    int sz, lst;
    vector<int> g[NS];
    SAM() {sz = lst = 1;}
    void insert(char c)
    {
        int a = ++sz, p = lst;
        e[a].mxl = e[p].mxl + 1, e[a].sz = 1, lst = a;
        while (!e[p][c] && p) e[p][c] = a, p = e[p].fa;
        if (!p) {e[a].fa = 1; return;}
        int q = e[p][c];
        if (e[q].mxl == e[p].mxl + 1) {e[a].fa = q; return;}
        int nq = ++sz;
        e[nq] = e[q], e[nq].mxl = e[p].mxl + 1, e[nq].sz = 0;
        e[a].fa = e[q].fa = nq;
        while (e[p][c] == q) e[p][c] = nq, p = e[p].fa;
    }
    void Dfs(int a)
    {
        int tmp = 0;
        for (int i = 0; i < g[a].size(); i += 1)
            Dfs(g[a][i]), tmp += e[g[a][i]].sz;
        for (int i = 0; i < g[a].size(); i += 1)
        {
            ans -= 1ll * e[g[a][i]].sz * (tmp - e[g[a][i]].sz) * e[a].mxl;
            ans -= 2ll * e[g[a][i]].sz * e[a].sz * e[a].mxl;
        }
        e[a].sz += tmp;
    }
    void run()
    {
        for (int i = 2; i <= sz; i += 1) g[e[i].fa].push_back(i);
        ans = 1ll * (n - 1) * (1ll * (1 + n) * n / 2);
        Dfs(1), printf("%lld\n", ans);
    }
} sam;

int main(int argc, char const* argv[])
{
    scanf("%s", str + 1), n = strlen(str + 1);
    for (int i = n; i >= 1; i -= 1) sam.insert(str[i]);
    sam.run();
    return 0;
}