题目链接：传送门
显然第一个情况和第二个情况不如第三个更优 并且他们可以避免，所以尽量构造第三种情况 将每个字符倒着插入trie树，因为先放后面的字符串是更优的 然后通过以字符结尾的点重构一棵树 在遍历这棵树的时候先走siz小的儿子一定更优，统计答案即可
#include <bits/stdc++.h> #define A 600010 using namespace std; typedef long long ll; int ch[A][26], n, ed[A], cnt, siz[A], ct; ll ans; char s[A]; void insert(char *s) { int len = strlen(s), rt = 0; for (int i = len - 1; i >= 0; i--) { int x = s[i] - 'a'; if (!ch[rt][x]) ch[rt][x] = ++cnt; rt = ch[rt][x]; } ed[rt] = 1; } vector<int> g[A]; void prepare(int fr, int last) { if (ed[fr]) g[last].push_back(fr), last = fr; for (int i = 0; i < 26; i++) if (ch[fr][i]) prepare(ch[fr][i], last); } void dfs(int fr) { siz[fr] = 1; for (int i = 0; i < g[fr].size(); i++) { int ca = g[fr][i]; dfs(ca); siz[fr] += siz[ca]; } } void work(int fr, int last) { int tim = ct++; ans += tim - last; sort(g[fr].begin(), g[fr].end(), [](int x, int y) {return siz[x] < siz[y];}); for (int i = 0; i < g[fr].size(); i++) { int ca = g[fr][i]; work(ca, tim); } } int main(int argc, char const *argv[]) { cin >> n; for (int i = 1; i <= n; i++) scanf("%s", s), insert(s); prepare(0, 0); dfs(0); work(0, 0); cout << ans << endl; }