题目描述就像做阅读理解一样...

首先看到后缀就心中不由得焦急，脑中浮现各种高级算法。

其实不然，这里其实没有用到过多的后缀性质，可以考虑转前缀，也就是把字符串反转。

让我们来理一下题意:

  1. 若在$x$之后存在是$\alpha$的后缀单词，那么就要付出$n*n$的代价来填$\alpha$。
  2. 若$\alpha $没有后缀，则填入代价为$x$。
  3. 在$[1,x-1]$中存在$\alpha $的后缀，下标最大的后缀位置为$y$，填入代价为$x-y$

第一种情况完全可以避免，不做考虑。

把最后构造的序列当成一棵树，

那么叶子节点一定包含它所有的后缀。

通过贪心可以证明，一定先填完一棵子树，才会去填另外一棵子树。

令$j$先于$i$填入，它们两个不属于同一棵子树，若现在$j$在$i$后填入，

那么$j$与它的父亲距离增加，$i$与$i$的孩子距离也增加，代价也就增加了。

同样地，可以通过不等式进行比较，证明子树小的先选。

接下来只需要考虑算法流程了。

反着建Trie树，统计结束结点，重新构造树，按上述方法统计答案即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=6e5+5;
struct Trie{int son[26],s;}t[N];
char s[N];int cnt;
void ins()
{
    int len=strlen(s+1),x=0;
    for(int i=len;i;i--)
    {
        int y=s[i]-'a';
        if(!t[x].son[y])t[x].son[y]=++cnt;
        x=t[x].son[y];
    }
    ++t[x].s;
}
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs0(int x,int fa)
{
    if(t[x].s)ins(fa,x),fa=x;
    for(int i=0;i<26;i++)
        if(t[x].son[i])dfs0(t[x].son[i],fa);
}
int siz[N];
void dfs(int x)
{
    siz[x]=1;
    for(int k=last[x],y;k;k=a[k].next)
        dfs(y=a[k].y),siz[x]+=siz[y];
}
int tmp=-1,q[N],r;ll ans;
bool cmp(int x,int y){return siz[x]<siz[y];}
void dfs1(int x,int lst)
{
    int nw=++tmp,l=r+1;
    ans+=tmp-lst;
    for(int k=last[x];k;k=a[k].next)
        q[++r]=a[k].y;
    if(l<r)sort(q+l,q+r+1,cmp);
    int rr=r;
    for(int i=l;i<=rr;i++)
        dfs1(q[i],nw);
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",s+1),ins();
    dfs0(0,0);
    dfs(0);
    dfs1(0,0);
    printf("%lld\n",ans);
    return 0;
}