题面：

给出一些单词，Lweb背诵每一个单词有以下情况：

1.如果某个单词后存在它的后缀，那他需要吃n*n颗泡椒才能学会。

2.如果在 1 …(x-1)的位置上的单词都不是它的后缀，那么他吃 x 颗泡椒就能记住它。

3.当它的所有后缀都被填入表内的情况下，如果在 1 …(x-1)的位置上存在是它后缀的单词， 所有是它后缀的单词中，序号最大为 y，那么他只要吃 x - y 颗泡椒就能把它记住。 要求在吃泡椒最少的情况下背完单词。

分析：

第一步

看到后缀这个东西我们会觉得很烦，所以不妨把每个单词都反转一下，这样后缀就能变成前缀，操作起来也更方便。

第二步

然后看到题目中要求寻找后缀(现在反转成了前缀)单词，我们就能想到建字典树。

第三步

基础工作做完了，现在考虑最优情况：

情况1要吃n*n颗泡椒，这明显是无论如何吃泡椒最多的选择，所以坚决不选。

情况2吃x颗泡椒，这种情况优一点，但和情况3比起来还是多吃了y颗泡椒，所以尽量多的用情况3背单词。

第四步

现在思考如何实现，情况3好想，找出不是任何单词前缀的单词，让它们最后背诵，先背完前缀的“前缀”，然后背完前缀，最后背整个单词。

这时候又会冒出不同单词前缀的字数，我们就从前缀少的子树背起，让自己前缀被记住时离自己近。最后把每棵子树要吃的泡椒数量加起来即可。

第五步

AC

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=610000;
ll n,id,ch[N][30],ed[N],ans,sz[N];char str[100010];
vector<ll>G[N];
void ins(char *s)
{
    ll p=0,len=strlen(s);
    for(ll i=len-1;i>=0;i--)
    {
        ll j=s[i]-'a';
        if(!ch[p][j])ch[p][j]=++id;
        p=ch[p][j];
    }
    ed[p]=1;
}//反转插入单词,方便找前缀(反转前的后缀) 
void dfs1(ll p,ll fa)
{
    if(ed[p])G[fa].push_back(p),fa=p;
    for(ll i=0;i<26;i++)if(ch[p][i])dfs1(ch[p][i],fa); 
}//建树
void dfs2(ll x)
{
    sz[x]=1;
    for(ll y:G[x])dfs2(y),sz[x]+=sz[y];
}//不是前缀的单词子树
bool cmp(ll a,ll b){return sz[a]<sz[b];}
void q(ll x,ll fa)
{
    ll xid=++id;
    ans+=xid-fa;
	//背诵当前单词需要吃的辣椒,fa为它的最近前缀y,用x的id减y的id 
    sort(G[x].begin(),G[x].end(),cmp);
	//拓扑排序让自己前缀被记住时离自己近
    for(ll y:G[x])q(y,xid);//计算每一单词 
}
int main()
{
    scanf("%lld",&n);
    id=0;memset(ch,0,sizeof ch);memset(ed,0,sizeof ed);ans=0;
    for(ll i=1;i<=n;i++)scanf("%s",str),ins(str);//输入+插入 
    dfs1(0,0);dfs2(0);//字符下标从0开始建树 
    id=0;q(0,1);
    printf("%lld\n",ans);
    return 0;
}

tip:比赛时用纯情况2骗了20分。。。

这题的核心其实就是字典树倒序处理后重构后缀树，然后按照子树大小排序求 dfn 序即可。

至于为什么要按子树大小排序请参考排队接水问题。

重构后缀树开个栈记录当前后缀节点即可。

答案就是所有节点的 dfn 序值减去他们的父亲的 dfn 序值之和。

还有别把字典树开成 char 了（我已经因为这个卡了很久，气笑了）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+10;
#define PII pair<int,int>
#define fi first
#define se second
int ch[N][26];
int siz[N],ed[N],v[N],fa[N],alen,ans,blen,clen;
void ins(string s)
{
	int len=s.size(),p=0;
	for(int i=len-1;i>=0;i--)
	{
		if(!ch[p][s[i]-'a'])ch[p][s[i]-'a']=++blen;
		p=ch[p][s[i]-'a'];
	}
	ed[p]=1;
}
stack<int>stk;vector<int>G[N];
void dfs1(int x)
{
	if(ed[x])
	{
		alen++;
		G[alen].push_back(stk.top());
		G[stk.top()].push_back(alen);
		stk.push(alen);
	}
	for(int i=0;i<26;i++)if(ch[x][i])dfs1(ch[x][i]);
	if(ed[x])stk.pop();
}
void dfs2(int x,int f)
{
	siz[x]=1;fa[x]=f;
	for(int y:G[x])if(y!=f)
	{
		dfs2(y,x);
		siz[x]+=siz[y];
	}
}
int dfn[N];
void dfs3(int x,int f)
{
	dfn[x]=++alen;
	vector<PII>vec;
	for(int y:G[x])if(y!=f)
		vec.push_back({siz[y],y});
	sort(vec.begin(),vec.end());
	for(auto i:vec)dfs3(i.se,x);
}
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;cin>>s;
		ins(s);
	}
	stk.push(0);dfs1(0);dfs2(0,0);dfs3(0,0);
	for(int i=1;i<=n;i++)ans+=dfn[i]-dfn[fa[i]];
	cout<<ans;
	return 0;
}

首先很多人第一时间想到的就是 Trie ，但是 Trie 是从前往后，记录的是前缀；

有聪明的小朋友就想到了，可以 反转字符串 ，这样就可以记录后缀了；

先对情况排序：

• 最好的就是第 $3$ 种，所有前缀都在前面，吃 $x-y$ 个泡椒 （其实最好是不吃） ;
• 其次就是第 $2$ 种，没有前缀，吃 $x$ 个泡椒（其实可以简单跟第一种归为一类，因为空串是所有字符串的前缀/）；
• 最差的就是第 $1$ 种，前面的前缀不全，就要吃 $n^2$ 的泡椒 （吃不吃得完都不一定） ；

所以对于任意字符串：前缀必须在该字符串前面；

因此我们需要构造一个树，去除 Trie 中没用的点 ，使得前缀的拓扑编号距离自己最大，即大子树放后拓扑。

###代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=610000,M=110000;
int n,id,ch[N][30],ed[N],ans;
void ins(string s){//Trie的正常插入 
    int p=0;
    for(int i=0;s[i];i++){
        int j=s[i]-'a';
        if(!ch[p][j]) ch[p][j] = ++id;
        p=ch[p][j];
    }
    ed[p] = 1;
}
vector<int> G[N];
void dfs1(int p,int fa){//重新建树，去除没用的点 
    if(ed[p])G[fa].push_back(p),fa=p;
    for(int i=0; i<26; i++)
        if(ch[p][i]) dfs1(ch[p][i], fa); 
}
int siz[N];
void dfs2(int x){//计算siz 
    siz[x]=1;
    for(int y:G[x]){
        dfs2(y);
        siz[x]+=siz[y];
    }
}
void solve(int x, int xfa){
    int xid=++id;
    ans+=xid-xfa;//编号距离 
    sort(G[x].begin(),G[x].end(),[](const int&n1,const int&n2){return siz[n1]<siz[n2];});//大子树放后拓扑
    for(int y:G[x])solve(y,xid);//拓扑 
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>n;
    id=0; memset(ch,0,sizeof(ch)); memset(ed,0,sizeof(ed));
    for(int i=1;i<=n;i++){
    	string s;
    	cin>>s;
    	reverse(s.begin(),s.end());//反转 
		ins(s);
	} 
    dfs1(0, 0);dfs2(0);
    id=ans=0;
    solve(0, 1);//拓扑 
    cout<<ans;
    return 0;
}

所有单词都反序，那么有以下三点： 1、如果某个单词后存在它的前缀，那他需要吃n*n颗泡椒才能学会； 解：这种情况太亏，一定要避免。所以安排顺序的时候，坚持“前缀在前”的原则。

2、如果在 1 …(x-1)的位置上的单词都不是它的前缀，那么他吃 x 颗泡椒就能记住它； 解：吃x个，也挺亏的。也要避免。 但避免了1 就避免了2 。

3、当它的所有前缀都被填入表内的情况下，如果在 1 …(x-1)的位置上存在是它前缀的单词， 所有是它前缀的单词中，序号最大为 y，那么他只要吃 x - y 颗泡椒就能把它记住。 解：前缀的拓扑编号距离自己最大，所以子树大的阶段放后拓扑。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=610000, M=110000;
int n, id, ch[N][30], ed[N];
LL ans;
char str[M];
void ins(char *s)
{
    int p=0, len=strlen(s);
    for(int i=len-1; i>=0; i--)
    {
        int j=s[i]-'a';
        if(!ch[p][j]) ch[p][j] = ++id;
        p=ch[p][j]; 
     
    }
    ed[p] = 1;
}
vector<int> G[N];
void dfs1(int p, int fa)
{
    if(ed[p]) G[fa].push_back(p), fa=p;
    for(int i=0; i<26; i++)
        if(ch[p][i]) dfs1(ch[p][i], fa); 
}
int siz[N];
void dfs2(int x)
{
    siz[x] = 1;
    for(int y : G[x])
    {
        dfs2(y);
        siz[x] += siz[y];
    }
}
bool cmp(int n1, int n2){ return siz[n1] < siz[n2];}
void solve(int x, int fa_id)
{
    int x_id = ++id;
    ans += x_id - fa_id;
    sort(G[x].begin(), G[x].end(), cmp);
    for(int y : G[x]) solve(y, x_id);
}
int main()
{
    scanf("%d", &n);
    id=0; memset(ch, 0, sizeof(ch)); memset(ed, 0, sizeof(ed));
    for(int i=1; i<=n; i++) scanf("%s", str), ins(str);
    dfs1(0, 0);
    dfs2(0);
    ans=0; id=0;
    solve(0, 1);
    printf("%lld\n", ans);
    return 0;
}

近视后人（如果你90分挂了#6）

十年OI一场空，______________。