Lweb 面对如山的英语单词，陷入了深深的沉思，”我怎么样才能快点学完，然后去玩三国杀呢？“。这时候睿智的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，他的计划册是长这样的：
—————序号 单词—————
1 2 ...... n-2 n-1 n—————
然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x 的单词（序号 1...x-1 都已经被填入）：
- 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n*n 颗泡椒才能学会；
- 当它的所有后缀都被填入表内的情况下，如果在 1...x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡椒就能记住它；
- 当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。
Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他记住这 n 个单词的情况下，吃最少的泡椒。
链接🔗
题解
处理后缀，我们可以将所有字符串串翻转，然后丢掉Trie中处理前缀
代价1是最不划算的，而且有办法完全避免，代价2 = 代价3
贪心策略，优先把前缀，优先把子树节点少的点放前面
将点抽出来单独建图，然后处理出每个点的儿子数量，然后在DFS求代价时，用排序优先算儿子数量小的点
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 510000;
const int maxc = 26;
char str[maxd];
struct
{
int arr[maxd][maxc],tot;
bool cnt[maxd];
void init()
{
tot=0;
memset(arr,-1,sizeof(arr));
memset(cnt,0,sizeof(cnt));
}
void insert(char *str)
{
int p = 0;int len = strlen(str);
for(int i=len-1;i>=0;i--)
{
if(arr[p][str[i]-'a'] == -1)
arr[p][str[i]-'a'] = ++tot;
p = arr[p][str[i]-'a'];
}
cnt[p] = 1;
}
}tree;
struct {
int v,next;
}e[100100];
int eid,f[100100],size[100100],pos,sw[100100];
long long ans;
void init()
{
memset(f,-1,sizeof(f));
eid=0;
}
void addedge(int x)
{
eid++;
e[eid].v = eid;
e[eid].next = f[x];
f[x] = eid;
}
void build(int x,int y) // 父亲节点，字典树编号
{
if(tree.cnt[y])
{
addedge(x);
x = eid;
}
for(int i=0;i<26;i++)
if(tree.arr[y][i]!=-1)
build(x,tree.arr[y][i]);
}
void getsize(int x)
{
size[x] = 1;
for(int i=f[x];i+1;i=e[i].next)
getsize(e[i].v),size[x]+=size[e[i].v];
}
bool cmp(int x,int y)
{
return size[x] < size[y];
}
void dfs(int x,int y) // 当前节点编号，上一节点坐标
{
pos++;
ans += pos-y;
y = pos;
int l = sw[0];
for(int i=f[x];i+1;i=e[i].next)
sw[++sw[0]] = e[i].v;
int r = sw[0];
sort(sw+l+1,sw+r+1,cmp);
for(int i=l+1;i<=r;i++) dfs(sw[i],y);
sw[0] = l;
}
int main()
{
int n;
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
init();
tree.init();
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",str);
tree.insert(str);
}
build(0,0);
getsize(0);
dfs(0,1);
printf("%lld",ans);
return 0;
}