[ZJOI2015]诸神眷顾的幻想乡（广义后缀自动机）

/*

题目中的神仙性质真的是令人愉悦

因为我一眼看成了每个点的度数不超过二十， 心想这他喵的和字符串什么关系

统计树上不同子串个数， 按道理直接dfs n次把所有的串插到后缀自动机里就行了

但是我们发现当我们从一个不是叶子的节点进行dfs时， 实际上得到的每一个串都是从某个叶子开始bfs产生的某个串的后缀

也就是说不是从叶子开始dfs是没啥用的

找出叶子然后暴力就好了 

*/

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define M 4000010

#define mmp make_pair

using namespace std;

int read()

{

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int ch[M][10], len[M], fa[M], cnt = 1, cor[100100], n, c;

vector<int> to[100010];

int insert(int lst, int c)

{

	int p = ++cnt, f = lst;

	len[p] = len[f] + 1;

	while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];

	if(f == 0)

		fa[p] = 1;

	else{

		int q = ch[f][c];

		if(len[q] == len[f] + 1)

		{

			fa[p] = q;

		}

		else

		{

			int nq = ++cnt;

			fa[nq] = fa[q];

			memcpy(ch[nq], ch[q], sizeof(ch[q]));

			len[nq] = len[f] + 1;

			fa[q] = fa[p] = nq;

			while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];

		}

	}

 	return p;

}

void dfs(int now, int lst, int pre)

{

	int tmp = insert(pre, cor[now]);

	for(int i = 0; i < to[now].size(); i++)

	{

		int vj = to[now][i];

		if(vj == lst) continue;

		dfs(vj, now, tmp);

	}

}

int main()

{

	n = read(), c = read();

	for(int i = 1; i <= n; i++) cor[i] = read();

	for(int i = 1; i < n; i++)

	{

		int vi = read(), vj = read();

		to[vi].push_back(vj);

		to[vj].push_back(vi);

	}

	for(int i = 1; i <= n; i++)

	{

		if(to[i].size() == 1)

		{

			dfs(i, i, 1);

		}

	}

 	ll ans = 0;

 	for(int i = 1; i <= cnt; i++) ans += len[i] - len[fa[i]];

	cout << ans << "\n";

	return 0;

}
巴特西

[ZJOI2015]诸神眷顾的幻想乡（广义后缀自动机）

最新文章

热门文章
