如果S的后缀在S后面，价代为 $N^2$，非常劣。

所以，S的后缀必须在S前面；而且符字串两两不同。把S全翻转，然后求前缀，这样比较便方。

如果S是T的前缀，就把S往T连一条边。

你意注到每个点的pos都会加好多次，减好多次。这个数系其实就是$indegree_i-outdegree_i$。

对了，其实每个T只需要往前找最短的前缀即可，大家请自行解理。

比如在现有 $\texttt{a}$ $\texttt{ab}$ $\texttt{abc}$，只需 $\texttt{a}$往 $\texttt{ab}$连， $\texttt{ab}$往 $\texttt{abc}$连即可。

lalalaooo

建树之后 $ans=val_i \times dfn_i$，因为序顺必须足满父亲要在儿子前面。

你要定确序顺。看起来像是每次取val最大的。但是这样实其不对。因为有可能你每次都取val大的，然而其实现在微稍取小一点的val，最终可以更优。

其实我们应照按子树大小排序。

因为比如说，你现在的根有两个儿子，一个非常大，一个是叶子，如果你先给大的分配，那个叶子就会献贡size大的+1 这么多，太多了。

相反，那个大的儿子只能节省1的献贡。

所以应该按照子树大小排序的方式定确遍历的式方。

lalalalaooo

题解写的越不细详，写的越好。

#include<bits/stdc++.h>
#define int long long
#define uint unsigned long long
using namespace std;
int n,ans1,ans2;
string s[100005];
int trie[510005][26],tot,fin[510005];
int head[100005],ver[600005],nxt[600005],idx=-1;
int ind1[100005],val[100005];
int ind2[100005];
priority_queue<pair<int,int> >q;
int sz[100005];

inline void makever(int x,int y);
inline void add(int x);
inline void makemap(int x);
inline void make1();
inline void make2();
void makesz(int u);

signed main() {
	std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	memset(head,-1,sizeof head);
	for(int i=1; i<=n; ++i) add(i);
	for(int i=1; i<=n; ++i) makemap(i);
	make1(),make2();
	cout<<min(ans1,ans2)<<"\n";
	return 0;
}

/*

送大家两组赛事造的样例 
5
a
ba
ca
da
bca


8
---
5
a
cba
ba
da
dcba


6
*/
inline void add(int x) {
	cin>>s[x];
	int p=0;
	for(int i=s[x].size()-1; i>=0; --i) {
		int ch=s[x][i]-'a';
		if(!trie[p][ch])trie[p][ch]=++tot;
		p=trie[p][ch];
	}
	fin[p]=x;
}
inline void makever(int x,int y) {
	++idx;
	ver[idx]=y;
	nxt[idx]=head[x];
	head[x]=idx;
}
inline void makemap(int x) {
	int p,mx,mxi;
	p=mx=mxi=0;
	for(int i=s[x].size()-1; i>=0; --i) {
		int ch=s[x][i]-'a';
		p=trie[p][ch];
		if(i&&fin[p]&&mx<s[fin[p]].size() ) { //从p结束的fin[p]是x的前缀
			mx=s[fin[p]].size(),mxi=fin[p];
		}
	}
	makever(mxi,x);
	++ind1[x],++ind2[x],--val[mxi],++val[x];
}
inline void make1() {
	q.push({0,0});
	int nw=-1;
	while(!q.empty()) {
		int u=q.top().second;
		q.pop();
		ans1+=(++nw)*val[u];
		for(int i=head[u]; ~i; i=nxt[i]) {
			int v=ver[i];
			if(!(--ind1[v])) {
				q.push({val[v],v});
			}
		}
	}
}
void makesz(int u) {
	sz[u]=1;
	for(int i=head[u]; ~i; i=nxt[i]) {
		int v=ver[i];
		makesz(v);
		sz[u]+=sz[v];
	}
}
inline void make2() {
	makesz(0);
	while(!q.empty())q.pop();
	q.push({sz[0],0});
	int nw=-1;
	while(!q.empty()) {
		int u=q.top().second;
		q.pop();
		ans2+=(++nw)*val[u];
		for(int i=head[u]; ~i; i=nxt[i]) {
			int v=ver[i];
			if(!(--ind2[v])) {
				q.push({-sz[v],v});
			}
		}
	}
}

赛时就差最后的贪心没想出来

首先对于所有没有有别的字符串为他的后缀的情况，我们发现他放在最前面是优的

然后对于有后缀的字符串，我们发现他的后缀一定在他的前面

然后我们考虑建图来表示，对每个字符串向他的最大的后缀连一条边，然后跑两遍dfs，第一次记录每个点的子树大小，第二次按从sz大小，每次先遍历sz最小的，他对答案的贡献就为，dfn序的差值

然后就做完了

code:

#include <bits/stdc++.h>
using namespace std;

bool mlest;

double tlest, tleed;

inline long long R(){
	long long x = 0, f = 1;char ch = getchar();
	while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}
	while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	return x * f;
}

inline void W(long long x){
	if(x < 0){x = -x;putchar('-');}
	if(x > 9) W(x/10);putchar(x%10+'0');
}

const long long N = 6e5 + 10;

long long n;

long long t[N][26];

long long ed[N];

string s[N];

long long dfn[N], dfncnt, cnt, sz[N];

vector<long long> e[N];

void add(long long u,long long v){
	e[u].push_back(v);
}

void read(){
	cin >> n;
	for(long long i = 1;i <= n; i++){
		cin >> s[i];
	}
	return ;
}

void insert(string s,long long id){
	long long u = 0;
	long long m = s.size() - 1;
	for(long long i = m;i >= 0; i--){
		long long x = s[i] - 'a';
		if(!t[u][x]) t[u][x] = ++cnt;
		u = t[u][x];
	}
	ed[u] = id;
}

long long get(string s,long long id){
	long long u = 0;
	long long ans = 0;
	long long m = s.size() - 1;
	for(long long i = m;i >= 1; i--){
		long long x = s[i] - 'a';
		u = t[u][x];
		if(ed[u]) ans = ed[u];
	}
	return ans;
}

void dfs1(long long u){
	sz[u] = 1;
	for(long long v : e[u]) {
		dfs1(v);
		sz[u] += sz[v];
	}
}

long long dfs2(long long u,int fa){
	dfn[u] = dfncnt++;
	long long ans = dfn[u] - dfn[fa];
	priority_queue<pair<long long,long long> ,vector<pair<long long,long long> >, greater<pair<long long,long long> > > q;
	for(long long v : e[u]){
		q.push({sz[v],v});
	}
	while(q.size()){
		long long v = q.top().second;
		q.pop();
		ans += dfs2(v,u);
	}
	return ans;
}

void init(){
	for(long long i = 1;i <= n; i++) insert(s[i],i);
}

void compute(){
	for(long long i = 1;i <= n; i++){
		add(get(s[i],i),i);
	}
	dfs1(0);
	W(dfs2(0,n+1));
}

void clear(){

}

void run() { read(); init(); compute(); clear(); }

bool mleed;

void wa() { cout << "\n" << tleed-tlest << "ms\n" << (&mleed-&mlest-1)/1024.0/1024.0 << "MB\n"; }

void fre(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

int main(){
//	fre("");
	tlest = clock();
	run();
	tleed = clock();
//	wa();
	return 0;
}