rt,对了#3,#4,#7三个点,代码如下:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,TR=510005;
int n,ans,tr[TR][26],tot,siz[TR],dfn[N],t;
vector <int> v[TR];
bool flag[TR];
string s[N];
void insert(string a)
{
int u=0;
for(int i=0;i<a.length();i++)
{
if(!tr[u][a[i]-'a'])
{
tr[u][a[i]-'a']=++tot;
v[u].push_back(tot);
}
u=tr[u][a[i]-'a'];
}
flag[u]=1;
}
bool cmp(int x,int y)
{
return siz[x]<siz[y];
}
void dfs_(int u)
{
siz[u]=1;
for(int i=0;i<v[u].size();i++)
{
int v2=v[u][i];
dfs_(v2);
siz[u]+=siz[v2];
}
}
void dfs(int u,int fa)
{
if(!flag[u])
{
for(int i=0;i<v[u].size();i++)
{
int v2=v[u][i];
dfs(v2,fa);
}
return ;
}
// cout<<u<<" "<<fa<<"\n";
dfn[u]=++t;
ans+=dfn[u]-dfn[fa];
for(int i=0;i<v[u].size();i++)
{
int v2=v[u][i];
dfs(v2,u);
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i];
reverse(s[i].begin(),s[i].end());
insert(s[i]);
}
dfs_(0);
for(int i=1;i<=tot;i++)
{
sort(v[i].begin(),v[i].end(),cmp);
}
// for(int i=1;i<=tot;i++) cout<<siz[i]<<" ";
dfs(0,0);
cout<<ans;
}