题意
给你n个完全不同的字符串，求将某些字符串改为其前缀，使得新的字符串集，依旧各不相同，且字符串总长度最小。
题解
首先我们字典树建树，字符串的末节点标记为1，这时候得到了一个只有0和1的树，为了将字符串总长度最小，我们肯定要尽量让1的节点在前。因此对于一个权值为0的节点，我们贪心的取其子树下深度最大的节点放置当前节点的位置，这样就可以满足字符串深度最低，所以我们利用multiset维护每个节点下1的深度。在计算答案的时候，对于每个节点，我们首先加上这个节点的子树的1的个数，若当前节点权值为0，则减去深度最大的节点到当前深度的差值，将所有的值求和即可。
（由于字符串总长度不超过10^5，我们直接暴力合并set即可，或者可以用set启发式合并）
AC代码
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<set>
#define N 100005
using namespace std;
typedef long long ll;
char a[N];
multiset<ll,greater<ll> >st[N];
multiset<ll,greater<ll> >::iterator it;
ll tree[N][26],End[N],size[N],tot,root,ans,all;
ll init(ll root)
{
for(ll i=0;i<26;i++)
tree[root][i]=-1;
End[root]=0;
return root;
}
void insert(char buf[])
{
ll l=strlen(buf),now=root;
for(ll i=0;i<l;i++)
{
if(tree[now][buf[i]-'a']==-1)tree[now][buf[i]-'a']=init(++tot);
now=tree[now][buf[i]-'a'];
}
End[now]++;
}
void dfs(ll now,ll deep)
{
size[now]=End[now];
for(ll i=0;i<26;i++)
{
if(tree[now][i]==-1)continue;
dfs(tree[now][i],deep+1);
size[now]+=size[tree[now][i]];
for(it=st[tree[now][i]].begin();it!=st[tree[now][i]].end();it++)
st[now].insert(*it);
}
if(now==0)return ;
ans+=size[now];
if(End[now])st[now].insert(deep);
else if(st[now].size())
{
ans-=*st[now].begin()-deep;
st[now].erase(st[now].begin());
st[now].insert(deep);
}
}
int main()
{
root=init(tot);
ll n;
scanf("%lld",&n);
for(ll i=0;i<n;i++)
{
scanf("%s",a);
insert(a);
}
dfs(root,0);
printf("%lld\n",ans);
}