dfs序最优性的证明真是曲折呢
给你一些字符串，让你对其进行排列，使得按以下规则花费最少(然而题意真的不清楚，很容易就让人以为字符串的顺序是排好的)
（$x$为字符串在自行排定的序列中的位置，当前字符串为$a$)
$1.$如果$a$存在后缀且a的后缀在a之后，花费$+=n^2$
$2.$如果$a$不存在后缀则花费$+=x$
$3.$设$y$为$a$之前离其最近的是$a$的后缀的字符串的位置，$a$存在后缀且$a$的后缀在$a$之前，则花费$+=x-y$
经过转化题意就比较显然了，但是我们如果仔细读题我们发现$1，2$规则其实完全没有必要。
规则1我们只要把$a$的后缀放在$a$之前就好了，这样肯定优于放在$a$的后面因为$x-y$的值最大只能是n-1显然优于$n^2$
规则2我们发现其实就是规则三中$y=0$的特殊情况，直接当规则3来处理就好
看到后缀我们显然首先想到的是后缀数组，但是本蒟蒻太弱了不会怎么办？？？（而且本蒟蒻也不知道本题能不能用后缀数组）
我们把字符串翻个顺序就会发现后缀其实就是前缀，所以我们可以翻转字符串，处理前缀。
而处理前缀我们首先就会想到$trie$字典树，所以本题我们采用建立$trie$字典树的做法。
看懂题目的规则之后我们发现可以贪心的求解此题，只要让字符串的后缀与字符串之间所隔的字符串数目最小即可
所以第一步我们建立一颗$trie$树
第二步我们发现一个字符串有可能有很多后缀，所以我们需要判重，这里使用并查集
由于字符串的后缀与字符串之间存在有向的关系，便建立一张有向图。$x->y$代表$x$是$y$的后缀
因为要保证字符串与字符串的后缀之间距离最小所以贪心的选取以x为根的最小的子树
（使用vector在算出每棵子树大小后进行排序即可）
最后按照规则求和
如果你有认真看我的或其他人的题解，你可以发现我们在最后求和的时候是按照dfs序的。那么为什么？（我不会）
所以我在夏令营时找了wqy神仙请教。
考虑建出一棵树之后，对于构建的任意合法的序列，都满足$i$的父亲一定在$i$之前出现，$i$的孩子们都一定在$i$之后出现
先尝试证明$dfs$序一定最优，对于以同一深度的节点为根的子树，在一颗中找一个叶子节点$j$,在另一颗里找一个根节点$i$(当前序列中$j$所在的子树的根在$i$之前出现
假设$j<i$的时候代价最小，尝试将$j$放在$i$的后面，此时$i<j$。那么我们发现如果$j$放在$i$与$i$的孩子们之间，$i$的孩子们和$i$的距离都会加$1$，所以总代价会增加，而$j$和$j$的父亲的距离一定也会增加，所以总代价也会增加
所以对于$j$所在子树的根比$i$在序列中出现的早的情况，$j<i$的情况是最优的
那么每个子树形成了一段连续的区间，对于每个节点进行调整，最后我们发现形成了一个$dfs$序(有时别的序列也会和$dfs$序列一样优秀，但是此处证明的是$dfs$序列是最优解之一，不是唯一解
接下来再证明先遍历子树小的更优秀。
$WQY$:
月明风清 $21:28:04$
因为你所有的$size$排序之后
月明风清 $21:28:17$
第$i$个根节点的贡献是前面所有树的$size$之和
所以要排序
综上所述，当我们进行$dfs$序且按子树大小排序时，求出代价即为最优。
$Q.E.D$
感谢$wqy$，给了我很大的帮助wucstdio
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 510050
#define M 100050
#define ll long long
ll ans=0;
char x[N];
int n,cnt,bo[N],tot=1,trie[5000050][27],fa[N],id[N],son[N],num;
vector<int>tu[N];
int read()
{
int s=0,p=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')p=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*p;
}
int find(int x)
{
if(fa[x]==x)return fa[x];
else return fa[x]=find(fa[x]);
}
void insert(char *s,int bh)
{
int l=strlen(s);
int u=1;
for(int i=l-1;i>=0;i--)
{
int c=s[i]-'a';
if(!trie[u][c])trie[u][c]=++tot;
u=trie[u][c];
}
bo[u]=bh;
}
void make(int x)
{
for(int i=0;i<26;i++)
{
int v=trie[x][i];
if(v)
{
if(!bo[v])
{
fa[v]=find(x);
}
else
{
tu[bo[find(x)]].push_back(bo[v]);
}
make(v);
}
}
}
int cmp(int x,int y)
{
return son[x]<son[y];
}
void sonsum(int x)
{
son[x]=1;
for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++)
{
int v=*it;
sonsum(v);
son[x]+=son[v];
}
sort(tu[x].begin(),tu[x].end(),cmp);
}
void dfs(int x)
{
id[x]=num++;
for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++)
{
int v=*it;
ans+=num-id[x];
dfs(v);
}
}
void dfss(int x)
{
for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++)
{
int v=*it;
cout<<v<<endl;
dfss(v);
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
scanf("%s",x);
insert(x,i);
}
for(int i=1;i<=tot;i++)fa[i]=i;
make(1); sonsum(0);dfs(0);
printf("%lld",ans);
return 0;
}并查集去重的思路来源于此篇blog
