[bzoj4567]-[SCOI2016]背单词

题目（BZOJ）
题目（洛谷）
 
首先咱们来反建串，这样后缀就转化为前缀问题。
因为这题不关心每个串的长度什么的，所以我们trie上那些空节点可以不要，这样就建好了一棵新树。
然后，对于问题中的条件1可以不管，因为代价太大，
剩下的条件2和3，直接在树上沿子树大小最小的开始走就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=100050;
const int M=500050;
ll ans;
struct node{
	int id;
	int val;
};
struct edge{
	int vk,nxt;
}e[M];
int head[M],tt;
inline void ad(int u,int v){e[++tt].vk=v;e[tt].nxt=head[u];head[u]=tt;}
inline bool cmp(const node &x,const node &y){
	return x.val<y.val;
}
int ch[M][27],vis[M],val[M],sz,no;
vector <node> son[M];
inline int idx(char c){return c-'a'+1;}
inline void insert(char *s){
	int n=strlen(s),u=1;
	for(int i=n-1;i>=0;--i){
		int c=idx(s[i]);
		if(!ch[u][c]){
			ch[u][c]=++sz;
		}
		u=ch[u][c];
	}
	vis[u]=1;
}
void dfs1(int fa,int u){
	int nxtfa=fa;
	if(vis[u])ad(fa,u),val[u]++,nxtfa=u;
	for(int i=1;i<=26;++i){
		if(!ch[u][i])continue;
		dfs1(nxtfa,ch[u][i]);
	}
}
void dfs2(int u){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].vk;
		dfs2(v);
		val[u]+=val[v];
		son[u].push_back((node){v,val[v]});
	}
	sort(son[u].begin(),son[u].end(),cmp);
}
void query(int u,int v){
	int nxtval=v;
	if(vis[u]){
		ans+=((++no)-v);
		nxtval=no;
	}
	for(int i=0;i<son[u].size();++i){
		int v=son[u][i].id;
		if(!v)break;
		query(v,nxtval);
	}
}
inline void data_clear(){no=0;sz=1;}
char s[M];
int n;
int main(){
	data_clear();
	read(n);
	for(int i=1;i<=n;++i){
		scanf(
		insert(s);
	}
	dfs1(1,1);
	dfs2(1);
	query(1,0);
	printf(
	return 0;
}