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;

}
巴特西

loj2012 「SCOI2016」背单词

最新文章

热门文章
