【做题日记】

P3294 [SCOI2016]背单词
贪心+Trie+dfs

贪心：对于一个串和他的前缀子串，尽可能把前缀放在前面

把后缀反向插转化为为前缀 trie插一遍
并查集重构树dfs求子树大小
按规则求和

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=500057;
int n,idx,val[N],tot,size[N],fa[N],id[N];
long long ans;
int ch[N][30];
char s[N];
vector<int>tree[N];
inline int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

inline void insert(char s[],int num)
{
	int p=0;
	for(int i=strlen(s)-1;i>=0;i--)
	{
		int u=s[i]-'a';
		if(!ch[p][u]) ch[p][u]=++idx;
		p=ch[p][u];
	}
	val[p]=num;
}
inline void remake(int now)
{
	
	for(int i=0;i<26;i++)
	{
		int ver=ch[now][i];
		if(!ver) continue;
	    if(!val[ver])
	    {
	    	fa[ver]=find(now);
		}
	    else
	    {
	    	tree[val[find(now)]].push_back(val[ver]);
		}
		remake(ver);
	}
}
bool cmp(int x,int y)
{
	return size[x]<size[y];
}
inline void make(int now)
{
	size[now]=1;
	for(int i=0;i<tree[now].size();i++)
	{
		make(tree[now][i]);
		size[now]+=size[tree[now][i]];
	}
	sort(tree[now].begin(),tree[now].end(),cmp);
}
inline void dfs(int now)
{
	id[now]=tot++;
	
	for(int i=0;i<tree[now].size();i++)
	{
		ans+=tot-id[now];
		dfs(tree[now][i]);
	}
	
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		insert(s,i);
	}
	for(int i=1;i<=idx;i++) fa[i]=i;
	remake(0);
	make(0);
	dfs(0);
	printf("%lld",ans);
	return 0;
}