loj2012 「SCOI2016」背单词

……

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef pair<int,int> par;
typedef long long ll;
int s[510005][26], n, len, cnt, idx[510005], hea[510005], qqq, siz[510005], orz;
int faq[510005];
ll ans;
char ss[510005];
vector<par> vec[510005];
struct Edge{
	int too, nxt;
}edge[1020005];
void add_edge(int fro, int too){
	edge[++qqq].nxt = hea[fro];
	edge[qqq].too = too;
	hea[fro] = qqq;
}
void dfs1(int x, int f){
	if(idx[x]){
		add_edge(x, f);
		add_edge(f, x);
		f = x;
	}
	for(int i=0; i<26; i++)
		if(s[x][i])
			dfs1(s[x][i], f);
}
void dfs2(int x, int f){
	siz[x] = 1;
	for(int i=hea[x]; i; i=edge[i].nxt){
		int t=edge[i].too;
		if(t==f)	continue;
		dfs2(t, x);
		siz[x] += siz[t];
		vec[x].push_back(make_pair(siz[t], t));
	}
	sort(vec[x].begin(), vec[x].end());
}
void dfs3(int x, int f){
	if(x)	faq[x] = ++orz;	
	for(int i=0; i<vec[x].size(); i++)
		dfs3(vec[x][i].second, x);
	ans += faq[x] - faq[f];
}
int main(){
	cin>>n;
	for(int i=1; i<=n; i++){
		scanf("%s", ss);
		len = strlen(ss);
		int u=0;
		for(int j=len-1; j>=0; j--){
			int t=ss[j]-'a';
			if(!s[u][t])	s[u][t] = ++cnt;
			u = s[u][t];
		}
		idx[u] = i;
	} 
	dfs1(0, 0);
	dfs2(0, 0);
	dfs3(0, 0);
	cout<<ans<<endl;
	return 0;
}