Description

Lweb 面对如山的英语单词，陷入了深深的沉思，“我怎么样才能快点学完，然后去玩三国杀呢？”。这时候睿智

的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，他的计划册是长这样的：

—————

序号 单词

—————

1

2

……

n-2

n-1

n

—————

然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x

的单词（序号 1...x-1 都已经被填入）：

1. 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n×n 颗泡椒才能学会；
2. 当它的所有后缀都被填入表内的情况下，如果在 1...x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡
   
   椒就能记住它；
3. 当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中
   
   ，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。
   
   Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他
   
   记住这 n 个单词的情况下，吃最少的泡椒。

Solution

正解：trie树+贪心

显然情况1是需要尽量不发生的，而且是可以避免的，只要把它的后缀都先加入即可

因为有相同后缀的要尽量在一起，所以在trie树上也就是连续一段，一直走即可

考虑到从一个节点往子树走的顺序只会影响到 父亲为该节点的儿子，所以满足局部最优，只要每次先走最小的子树即可.

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <queue>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef long long ll;

const int N=510005;

int n,cnt=0,sz[N],ch[N][27],w[N];char s[N];

inline void ins(){

	scanf("%s",s);

	int len=strlen(s),p=0;

	for(int i=len-1;i>=0;i--){

		int x=s[i]-'a';

		if(!ch[p][x])ch[p][x]=++cnt;

		p=ch[p][x];

	}

	w[p]++;

}

struct node{

	int x,v;

	bool operator <(const node &pr)const{return v>pr.v;}

};

int head[N],nxt[N*26],to[N*26],num=0;

inline void link(int x,int y){

	nxt[++num]=head[x];to[num]=y;head[x]=num;

}

int id=0;ll ans=0;

inline void dfs(int x,int last){

	int now=0;

	if(x)id++,ans+=id-last,now=id;

   priority_queue<node>q;

	for(int i=head[x];i;i=nxt[i])

		if(to[i])q.push((node){to[i],sz[to[i]]});

	while(!q.empty()){

		int u=q.top().x;q.pop();

		dfs(u,now);

	}

}

inline void build(int x,int last){

	if(w[x])link(last,x);

	for(int i=0;i<=25;i++){

		int u=ch[x][i];

		if(u)build(u,w[x]?x:last);

	}

}

inline void getit(int x){

	sz[x]=1;

	for(int u,i=head[x];i;i=nxt[i])

		u=to[i],getit(u),sz[x]+=sz[u];

}

void work()

{

	scanf("%d",&n);

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

	build(0,0);getit(0);

	dfs(0,0);

	cout<<ans<<endl;

}

int main()

{

	freopen("pp.in","r",stdin);

	freopen("pp.out","w",stdout);

	work();

	return 0;

}