题意
给你 \(n\) 个字符串，让你对其进行排列，使得按以下规则花费最少：
设当前字符串为 \(s\)，\(x\) 为 \(s\) 在答案排列中的位置。
-
如果 \(s\) 存在后缀且 \(s\) 的后缀在 \(s\) 之后，花费加 \(n^2\)。
-
如果 \(s\) 不存在后缀则花费加 \(x\)。
-
设 \(y\) 为 \(s\) 之前离其最近的是 \(s\) 的后缀的字符串的位置，\(s\) 存在后缀且 \(s\) 的后缀在 \(s\) 之前，则花费加 \(x-y\)。
解法
对于 1 条件，显然尽量不要满足，因为 1 条件的花费永远比 2、3 条件多。
对于 2 条件，可以视为 3 条件中 \(y=0\)，因此和 \(3\) 条件合并。
所以可以有一个贪心策略，对于一个字符串 \(s\)，将它的若干后缀字符串放在 \(s\) 之前。那么此时仅存在 3 条件。
题目需要维护后缀，那么可以考虑将字符串反转，变成前缀，于是也可以想到对于反转的字符串建立 Trie 树。
既然要满足贪心策略，那么在 Trie 中，每一个字符串结尾的结点要在它的祖先结点之后。Trie 树就可以维护排列中的先后关系。
3 条件的花费为 \(x-y\)，即排列中的距离，那么在 Trie 中，每一个字符串的结尾结点才需要考虑，因此考虑重构 Trie，将不是字符串结尾的结点删去。
考虑另一个贪心策略，由于 3 条件花费为 \(x-y\)，那么 \(x\) 和 \(y\) 的距离越近越好，所以最优策略中的 \(x\) 和 \(y\) 在重构树中一定是父子关系。
由于我们需要 \(x-y\) 最小，所以我们尽可能地让 \(x\) 和 \(y\) 放一起，也就是遍历完父亲就遍历儿子。可以发现，这样的遍历顺序就是 dfs 序。
此时我们得到最优的遍历顺序为 dfs 序，对于一个结点 \(x\)，可以发现在 dfs 序下，它和父节点的距离为之前遍历过的兄弟结点的子树大小和，也就是花费，因此可以对每一个结点按子树大小排序，即可得到最优解。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int n, trie[N][27], cnt, last[N], siz[N], dfn, ans;
bool End[N];
vector<int> e[N];
void insert(string s)
{
int x = 0;
for(int _ = 0; _ < s.size(); _++)
{
char i = s[_];
if(!trie[x][i - 'a'])
trie[x][i - 'a'] = ++cnt;
x = trie[x][i - 'a'];
}
End[x] = true;
return;
}
void rebuild(int x)
{
if(End[x] && x)
{
e[last[x]].push_back(x);
last[x] = x;
}
for(auto y : trie[x])
{
if(!y)
continue;
last[y] = last[x];
rebuild(y);
}
return;
}
void dfs(int x)
{
siz[x] = 1;
for(auto y : e[x])
{
dfs(y);
siz[x] += siz[y];
}
sort(e[x].begin(), e[x].end(), [](int x, int y)
{
return siz[x] < siz[y];
});
return;
}
void dfs1(int x)
{
int k = dfn;
dfn++;
for(auto y : e[x])
{
ans += dfn - k;
dfs1(y);
}
return;
}
signed main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
string s;
cin >> s;
reverse(s.begin(), s.end());
insert(s);
}
End[0] = true;
rebuild(0), dfs(0), dfs1(0);
cout << ans;
return 0;
}