题目描述
Lweb 面对如山的英语单词，陷入了深深的沉思，”我怎么样才能快点学完，然后去玩三国杀呢？“。这时候睿智的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，他的计划册是长这样的：
—————序号 单词—————
1 2......n-2n-1 n—————
然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x 的单词（序号 1...x-1 都已经被填入）：
1) 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n*n 颗泡椒才能学会；
2) 当它的所有后缀都被填入表内的情况下，如果在 1...x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡椒就能记住它；
3) 当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。
Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他记住这 n 个单词的情况下，吃最少的泡椒。
--by luogu
http://daniu.luogu.org/problem/show?pid=3294
不是很懂四川人对泡椒的热情；
倒置单词，然后建trie
首先可以肯定第一种情况不存在；
看一眼trie树发现只要按trie背单词总不会有情况一
用trie树建立一棵表示单词后缀关系的新树；
（相当于把没有is_end标记的点缩去）
然后有两个性质：
1，背完整棵子树再背其他；
2，先背小的子树；
暴力排序并dfs即可；
（upd:泡椒真尼玛好吃）
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct ss{
int next,to;
}tree[];
int first[],num,size[];
int sor[],dfn[];
struct Trie{
int ch[];
int flag;
};
Trie trie[];
int tot,n;
char s[];
long long ans=;
int dfs_1(int ,int );
void build(int ,int );
void dfs_2(int ,int ,int );
bool cmp(int ,int );
int main()
{
int i,j,k,len;;
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%s",s);
len=strlen(s);
k=;
for(j=len-;j>=;j--){
if(!trie[k].ch[s[j]-'a'])
trie[k].ch[s[j]-'a']=++tot;
k=trie[k].ch[s[j]-'a'];
}
trie[k].flag=;
}
n=;
dfs_1(,);num=;
dfs_2(,,);
printf("%lld\n",ans);
return ;
}
int dfs_1(int now,int fa){
int j=,k;
if(trie[now].flag||now==)k=++n;
for(int i=;i<=;i++)
if(trie[now].ch[i])
j+=dfs_1(trie[now].ch[i],trie[now].flag?k:fa);
if(trie[now].flag&&now)
size[k]=++j,build(fa,k);
return j;
}
void build(int f,int t){
tree[++num].next=first[f];
tree[num].to=t;
first[f]=num;
}
void dfs_2(int now,int fa,int str){
int i,j=str,k;
dfn[now]=++num;
ans+=dfn[now]-dfn[fa];
for(i=first[now];i;i=tree[i].next)
sor[++j]=i;
sort(sor+str+,sor+j+,cmp);
for(i=str+;i<=j;i++){
dfs_2(tree[sor[i]].to,now,j);
}
}
bool cmp(int a,int b){
return size[tree[a].to]<size[tree[b].to];
}