这题乍一看是排序贪心，然后使用领项交换来做题
由于有了第一条规则的存在，因为\(n*n\)远大于另外两条规则所产生的代价，所以我们不会让后缀排在后面
于是乎，我们倒序建立trie树并且重构树（具体可见洛谷题解），那么问题就转换为
给这棵树标号，要求必须标了父亲才能标儿子，令每一条边的代价为儿子的序号减去父亲的序号，要求所有边代价和最少
如果按照领项交换做题，就可以得出一个方案：每次标记时，优先标记直接儿子数最少的节点
因为对一个有\(n\)个儿子的节点，在最终的序列中把他往后面移动一位（注意移动后也要满足父亲在儿子的前面，所以后面一个节点不可能是这个被移动节点的儿子），答案会减去\(n-1\)（注意这个\(-1\)是因为这个被移动节点到其父亲的距离要加\(1\)），那么后面那个节点被移动到了前一位也相同计算，可得出上述方案
但这种方法是错的，比如对于数据
7
a
ba
cba
dba
e
ge
fe
如果按照这种方法排序，得出来的序列为
a
e
fe
ge
ba
cba
dba
但实际上正确序列应该为
e
fe
ge
a
ba
cba
dba
究其原因，是因为我们刚刚的证明只能说明对于最优的排序，一定不会存在相邻的两项，前一项的直接儿子数更多（不信验证一下，上述两个排列都满足这个性质）。但是满足这个性质的不一定是最优排序
那为啥国王游戏那一道题目可以？就看我最后的手写批注喽
这题由于多了一个限制（父亲必须在儿子前面），是二维排序，就不能用邻项交换了（以后多维的都别用吧）
所以这题目是一个树上贪心
那么这个模型可以背下来（因为有些证明不是很清楚，希望有大佬或者ACM队友可以解惑），以下是解法
首先我们感性理解一个性质，就是对一个树，有一个根节点，他有若干颗子树，一定会在标记完了一整颗子树后才会去标记另一颗子树
因为边的代价只与父子标号之差有关，所以每个父子挨得越近越好，就不要中间插其他的了
那么有了这个性质，我们不妨每颗子树都已经标记完毕了，在考虑如何对各个子树排序
这就是一个简单的排队打水问题，规模越小的子树越靠前即可
code：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int trie[N*5][30];
int tot=1,n;
int flag[N*5];
ll ans;
int pos[N],fa[N],sz[N];
vector<int> G[N];
char s[N*5];
bool cmp(int a,int b)
{
return sz[a]<sz[b];
}
void insert(char *str,int k)
{
int len=strlen(str),p=1;
for(int i=len-1;i>=0;i--)
{
if(!trie[p][str[i]-'a']) trie[p][str[i]-'a']=++tot;
p=trie[p][str[i]-'a'];
}
flag[p]=k;
}
void dfs(int p,int k)
{
if(flag[p])
{
G[k].push_back(flag[p]);
fa[flag[p]]=k;
}
for(int i=0;i<26;i++)
if(trie[p][i]) {
if(flag[p]) dfs(trie[p][i],flag[p]);
else dfs(trie[p][i],k);
}
}
void dp(int p)
{
sz[p]=1;
int len=G[p].size();
for(int i=0;i<len;i++)
{
dp(G[p][i]);
sz[p]+=sz[G[p][i]];
}
sort(G[p].begin(),G[p].end(),cmp);
}
void solve(int p,int cnt)
{
pos[p]=cnt;
ans+=cnt-pos[fa[p]];
int len=G[p].size(),num=1;
for(int i=0;i<len;i++)
{
solve(G[p][i],cnt+num);
num+=sz[G[p][i]];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
insert(s,i);
}
dfs(1,0);
dp(0);
solve(0,0);
printf("%lld",ans);
return 0;
}