【bzoj4567】[Scoi2016]背單詞

這道題發現顯然是讓字尾在前面，兒子較大的先放最優

一個trie就解決問題。（但是我size一開始寫錯卡了n久）

#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 610009
using namespace std;
int n,b[N];
ll Ans;
char a[N];
bool cmp(const int &x,const int &y);
struct Trie
{
	int son[N][26],cnt,size[N],danger[N],top,so[N],fa[N],first[N];
	int number;
	ll pos[N],P;
	struct edge
	{
		int to,next;
		edge(int x=0,int y=0):to(x),next(y){}
	}e[N];
	void add(int x,int y)
	{
		e[++number]=edge(y,first[x]);
		first[x]=number;
		fa[y]=x;
	}
	void init()
	{
		cnt=1,number=top=P=0;
		for (int i=0;i<26;i++) son[0][i]=cnt;
	}
	void add(int a[],int len)
	{
		int now=1;
		for (int i=1;i<=len;i++)
		{
			if (!son[now][a[i]]) son[now][a[i]]=++cnt;
			now=son[now][a[i]];
		}
		size[now]=danger[now]=1;
	}
	void get(int x,int last)
	{
		if (danger[x]) add(last,x),last=x;
		for (int i=0;i<26;i++)
			if (son[x][i]) get(son[x][i],last);
		if (danger[x])
			for (int i=first[x];i;i=e[i].next)
				size[x]+=size[e[i].to];
	}
	ll dfs(int x)
	{
		if (!danger[x]) pos[x]=pos[fa[x]];
		else pos[x]=++P;
		int l=top+1,r=top;
		ll ans=pos[x]-pos[fa[x]];
		for (int i=first[x];i;i=e[i].next)
			if (e[i].to) so[++r]=e[i].to;
		sort(so+l,so+r+1,cmp);
		top=r;
		for (int i=l;i<=r;i++)
			ans+=dfs(so[i]);
		top=l-1;
		return ans;
	}
}trie;
bool cmp(const int &x,const int &y)
{
	return trie.size[x]<trie.size[y];
}
int read()
{
	int x=1;
	char ch;
	while (ch=gc,ch<'0'&&ch>'9') if (ch=='-') x=-1;
	int s=ch-'0';
	while (ch=gc,ch<='9'&&ch>='0') s=s*10+ch-'0';
	return s*x;
}
int main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	trie.init();
	n=read();
	for (int i=1;i<=n;i++)
	{
		scanf("%s",a+1);
		int len=strlen(a+1);
		for (int i=1;i<=len;i++) b[i]=a[len-i+1]-'a';
		trie.add(b,len);
	}
	trie.get(1,1);
	Ans=trie.dfs(1);
	printf("%lld\n",Ans);
	return 0;
}