LOJ #2012. 「SCOI2016」背单词

题目链接：​​传送门​​

显然第一个情况和第二个情况不如第三个更优
并且他们可以避免，所以尽量构造第三种情况
将每个字符倒着插入trie树，因为先放后面的字符串是更优的
然后通过以字符结尾的点重构一棵树
在遍历这棵树的时候先走siz小的儿子一定更优，统计答案即可

#include <bits/stdc++.h>
#define

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;
}