分析

非常好的思维题。我们发现第一条件完全没有用，其实就是要求我们，使每个串的后缀必须先于该串出现。那么我们可以根据后缀来构成一个拓扑图。那么现在问题就是求，求出一个拓扑图的遍历顺序，要求 这个最小。我们发现最小代价的遍历顺序，那么一个点的贡献就是 。那么我们优先 的 来遍历一定是最优的。

• 如何构建新图。我们考虑把所有串反序插入。那么在 树上，节点 是 的父亲，那么就要连一条 的单向边。这个很好理解，因为反序插入之后如果一个节点是另一个节点父亲或者祖先。那么它一定是作为后缀出现的。这里我们可以考虑用并查集来维护所有 上的结束节点。

• 新图上的求解，先进行一次 ，将所有节点的 求出来。那么再对所有儿子排个序，最后贪心的通过 最小的 就好了。总的时间复杂度为 。

• 思路非常好，要深度分析条件。而且考察的代码难道也不高。难得的好题。

  代码

#include<bits/stdc++.h>
using namespace std;
const int N = 6e5 + 100;
int ch[N][26],fa[N],size,n,Id[N],si[N],vis[N];
char S[N];
vector<int> G[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void ins(char *s,int op) {
    int len = strlen(s + 1);int u = 0;
    for(int i = len;i >= 1;i--) {
        int c = s[i] - 'a';
        if(!ch[u][c]) ch[u][c] = ++size;
        u = ch[u][c];
    }
    vis[u] = op;
} 
void make(int u) {
    for(int i = 0;i < 26;i++) {
        int v = ch[u][i];
        if(v) {
            if(!vis[v]) fa[v] = find(u);
            else G[vis[find(u)]].push_back(vis[v]);
            make(v);
        }
    }
}
bool cmp(int a,int b) {return si[a] < si[b];}
void dfs(int u) {
    si[u] = 1;for(auto v:G[u]) dfs(v),si[u] += si[v];
    sort(G[u].begin(),G[u].end(),cmp);
}
long long ans = 0;
void solve(int u) {
    Id[u] = size++;for(auto v:G[u]) {ans += size - Id[u];solve(v);}
}
int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%s",S+1);ins(S,i);
    }
    for(int i = 1;i <= size;i++) fa[i] = i;
    make(0);dfs(0);size = 0;solve(0);
    printf("%lld\n",ans);
}