题目描述
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 个单词的情况下，吃最少的泡椒。
输入输出格式
输入格式：
输入一个整数 n ，表示 Lweb 要学习的单词数。接下来 n 行，每行有一个单词（由小写字母构成，且保证任意单词两两互不相同）1<=n<=100000, 所有字符的长度总和 1<=|len|<=510000
输出格式：
Lweb 吃的最少泡椒数
题意：略；
①跟单词后缀有关，把单词反向插入字典树，则原题变成给字典树上的节点一个顺序，对于一个节点，如果在它的前驱节点上有一个编号比它大的节点则代价为n*n,没有的话就为当前节点编号减去往上数的最大节点的编号（把字典树的根节点看成是0号点）
②在字典树上贪心，让dfs为编号顺序，每次选择子树大小较小的节点先进入，因为这样可以让后面的节点的大小尽量小。
(我说的很不严谨，大概是自己不太清楚证明)
#include<bits/stdc++.h>
using namespace std;
const int N = ,M = ;
char *s,P[M];
int n,ch[M][],sz=,top[M],size[M],idx[M],val[M],t;
long long ans;
vector<int>E[M];
char gc(){
static char *p1,*p2,s[];
if(p1==p2) p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
int rd(){
int x = ; char c = gc();
while(c<''||c>'') c = gc();
while(c>=''&&c<='') x=x*+c-'',c=gc();
return x;
}
int gt(char *c){
char *st = c;
do *c=gc(); while(*c<'a'||*c>'z');
do *++c=gc(); while(*c>='a'&&*c<='z');
*c = ;
return c - st;
}
int dfs1(int u){
if(val[u]) {E[top[u]].push_back(u); top[u] = u;}
for(int i = ,v;i < ;i++){
if(ch[u][i]){
top[v=ch[u][i]] = top[u];
size[u] += dfs1(v) + bool(val[v]);
}
}
return size[u];
}
bool cmp(int a,int b){return size[a]<size[b];}
void dfs2(int u){
sort(E[u].begin(),E[u].end(),cmp);
for(int i = ,v;i < E[u].size();i++){
idx[v=E[u][i]] = ++t;
ans += t - idx[u];
dfs2(v);
}
}
int main()
{ freopen("bzoj4567.in","r",stdin);
freopen("bzoj4567.out","w",stdout);
n=rd();
for(int i = ,l,k;i <= n;i++){
s = P; l = gt(s+); k = ;
for(int i = l;i >= ;i--) {
if(!ch[k][s[i]-'a']) ch[k][s[i]-'a'] = ++sz;
k = ch[k][s[i]-'a'];
}
val[k] = ;
}
top[] = ;
dfs1();
dfs2();
printf("%lld\n",ans);
return ;
}//by tkys_Austin;