Description：

给 $n$ 个字符串，不同的排列有不同的代价，代价按照如下方式计算（字符串 $s$ 的位置为 $x$ ）：

$1$ 、排在 $s$ 后面的字符串有 $s$ 的后缀，则代价为 $n^2$ ；

$2$ 、排在 $s$ 前面的字符串有 $s$ 的后缀，没有排在 $s$ 后面的 $s$ 的后缀，则代价为 $x-y$ （ $y$ 为最后一个 $s$ 的后缀的位置）；

$3$ 、 $s$ 没有后缀，则代价为 $x$ 。

求最小代价和。

$1\leqslant n\leqslant 100000,1\leqslant \sum L\leqslant 500000$

Solution：

看了半天题解，首先把字符串反转，后缀转成前缀，这样就可以用 $trie$ 来维护，然后又发现第一种情况是怎么样都不会有的，所以一个串的前缀一定排在他之前，也就是说 $trie$ 树上他的祖先标号一定比他小，然后剩下的就是按怎样的顺序遍历子树，因为我们只要知道有标号的（是某个字符串结尾的）点的关系，所以应该把不是这样的点去掉，不然会影响我们进入那个子树，如果两个串都在同一个子树中但是不存在前缀关系，那他们也是无关的，题解用了一个很神奇的方法，用并查集把所有没用的点合并起来，具体看代码，然后这样就可以贪心了，因为子树互相无关，子树内互相有关，不难发现每次一定按 $siz$ 从小到大的顺序遍历子树，因为要让这个点的儿子与这个点标号的差的和尽量小。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

#define MAXL 500010

char c[MAXL];

int pos[MAXL];

struct node

{

	int tr[26];

	int siz;

	node(){siz = 0;}

}t[MAXL];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void add(int id,char c[])

{

	int cur = root;

	int l = strlen(c + 1);

	for(int i = 1;i <= l;++i)

	{

		if(t[cur].tr[c[i] - 'a'] == 0)

			t[cur].tr[c[i] - 'a'] = newnode();

		cur = t[cur].tr[c[i] - 'a'];

		++t[cur].siz;

	}

	pos[cur] = id;

	return;

}

int dfn[MAXL],tot = 0;

long long ans = 0;

vector<int> g[MAXN];

int f[MAXL];

int find(int k){return (f[k] == -1 ? k : f[k] = find(f[k]));}

void rebuild(int k)

{

	for(int i = 0;i < 26;++i)

	{

		if(t[k].tr[i] == 0)continue;

		if(pos[t[k].tr[i]] == 0)f[t[k].tr[i]] = find(k);

		else g[pos[find(k)]].push_back(pos[t[k].tr[i]]);

		rebuild(t[k].tr[i]);

	}

	return;

}

int siz[MAXL];

bool cmp(int a,int b){return siz[a] < siz[b];}

void calc(int k)

{

	siz[k] = 1;

	for(int i = 0;i < g[k].size();++i)

	{

		calc(g[k][i]);

		siz[k] += siz[g[k][i]];

	}

	return;

}

void dfs(int k,int cur)

{

	dfn[k] = tot++;

	ans += dfn[k] - cur;

	cur = dfn[k];

	sort(g[k].begin(),g[k].end(),cmp);

	for(int i = 0;i < g[k].size();++i)

	{

		dfs(g[k][i],cur);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%s",c + 1);

		int l = strlen(c + 1);

		for(int x = 1,y = l;x < y;++x,--y)swap(c[x],c[y]);

		add(i,c);

	}

	memset(f,-1,sizeof(f));

	rebuild(root);

	calc(root);

	dfs(root,0);

	cout << ans << endl;

	return 0;

}