题目
题目描述
Lweb 面对如山的英语单词，陷入了深深的沉思，”我怎么样才能快点学完，然后去玩三国杀呢？“。这时候睿智的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，他的计划册是长这样的：
—————序号 单词—————
1 2……n-2n-1 n—————
然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x 的单词（序号 1…x-1 都已经被填入）：
- 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n*n 颗泡椒才能学会；
- 当它的所有后缀都被填入表内的情况下，如果在 1…x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡椒就能记住它；
- 当它的所有后缀都被填入表内的情况下，如果 1…x-1的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。
Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他记住这 n 个单词的情况下，吃最少的泡椒。
输入输出格式
输入格式：
输入一个整数 n ，表示 Lweb 要学习的单词数。
接下来 n 行，每行有一个单词（由小写字母构成，且保证任意单词两两互不相同）1<=n<=100000, 所有字符的长度总和 $1<=\vert len\vert<=510000$
输出格式：
Lweb 吃的最少泡椒数
输入输出样例
输入样例#1：
2
a
ba
输出样例#1：
2
题解
根据题目中的要求，发现限制$1$绝对不能有，根据限制$3$，如果$a$是$b$的最长后缀，让$ab$序号放在一起是最优策略（当前）
设$x$点有$k$个后缀，第$i$个后缀代表的子树大小为$a_i$，那么产生的代价为$k+(k-1)a_1+(k-2)a_2+…+a_n$，这样让$a$从小到大排即为最优解
我也不知道这样对不对反正写了一下过了不管了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e6+5;
struct p{
int x,y;
bool operator< (const p &a)
const{
return x<a.x;
}
}c[MAX];
int n,tot=1,num,cnt=-1;
LL ans;
int h[MAX],id[MAX],siz[MAX];
char a[MAX];
void add(int x,int y) {c[++num]=(p){h[x],y},h[x]=num;}
struct Trie{
int fl[MAX];
int son[MAX][26];
void ins(int id,int _n)
{
int x=1;
for(int i=_n;i>=1;--i)
if(son[x][a[i]-'a']) x=son[x][a[i]-'a'];
else son[x][a[i]-'a']=++tot,x=tot;
fl[x]=id;
}
void dfs(int x=1,int F=0)
{
if(fl[x]) add(F,fl[x]);
for(int i=0;i<26;++i)
if(son[x][i]) dfs(son[x][i],fl[x]?fl[x]:F);
}
}Tree;
void Dfs(int x=0,int fa=0)
{
siz[x]=1;
for(int i=h[x];i;i=c[i].x)
Dfs(c[i].y,x),siz[x]+=siz[c[i].y];
}
void dfs(int x=0,int fa=0)
{
id[x]=++cnt,ans+=id[x]-id[fa];
vector<p> vec;
for(int i=h[x];i;i=c[i].x)
vec.push_back((p){siz[c[i].y],c[i].y});
sort(vec.begin(),vec.end());
for(int i=0,cnt=vec.size();i<cnt;++i)
dfs(vec[i].y,x);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%s",a+1),Tree.ins(i,strlen(a+1));
return Tree.dfs(),Dfs(),dfs(),printf("%lld",ans),0;
}
