题目大意：
给出总长度不超过1E+5的不重复字符串集，给每个字符串选一个前缀使得可以区分它。
题目分析：
KAN出的DIV2难度一般不高，想升Ranting的可以试试。
简单的树上启发式合并，建出Trie树，一开始每个字符串用自己表示，每次向上合并的时候选出堆中最大元素变成当前位置，特判一下有end的地方即可。
证明也很简单，我们考虑一个根没被选的子树，若我们要使得这个子树的代价最小，那么我们一定要选择一个位置放到根上来，不难发现选择深度最大的点是会最小的。由于树的子结构的关系，这样向上归纳也是正确的。
代码：
#include<bits/stdc++.h>
using namespace std; const int sigma = ; int n,num,len,root;
char str[];
struct trie{
int end,sz,nxt[];
}T[]; int Num(char ch){return ch-'a';} void insert(int now,int pla){
if(pla == len) {T[now].sz++;T[now].end=;return;}
int um = Num(str[pla]);
if(T[now].nxt[um]){
insert(T[now].nxt[um],pla+);
}else{
num++; T[now].nxt[um] = num;
insert(T[now].nxt[um],pla+);
}
} void dfs(int now){
for(int i=;i<sigma;i++)
if(T[now].nxt[i]) dfs(T[now].nxt[i]),T[now].sz+=T[T[now].nxt[i]].sz;
} void read(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",str);
len = strlen(str);
insert(root,);
}
dfs(root);
} int ans = ;
int bel[];
priority_queue<int,vector<int>,less<int> > q[]; int merge(int a,int b){
if(q[a].size()<q[b].size()){
while(!q[a].empty()){
int k = q[a].top();q[a].pop();
q[b].push(k);
}
return b;
}else{
while(!q[b].empty()){
int k = q[b].top();q[b].pop();
q[a].push(k);
}
return a;
}
} void dfs2(int now,int val){
int flag = false;
for(int i=;i<sigma;i++){
if(T[now].nxt[i]) flag=true,dfs2(T[now].nxt[i],val+);
}
if(!flag){bel[now]=++num;q[num].push(val);return;}
for(int i=;i<sigma;i++){
if(T[now].nxt[i]){
if(bel[now]){bel[now]=merge(bel[now],bel[T[now].nxt[i]]);}
else bel[now] = bel[T[now].nxt[i]];
}
}
if(T[now].end){
q[bel[now]].push(val);
}else{
q[bel[now]].pop();
q[bel[now]].push(val);
}
} void work(){
num = ;
for(int i=;i<sigma;i++){
if(!T[root].nxt[i]) continue;
dfs2(T[root].nxt[i],);
int hh = bel[T[root].nxt[i]];
while(!q[hh].empty()){
ans += q[hh].top();q[hh].pop();
}
}
printf("%d",ans);
} int main(){
read();
work();
return ;
}