【BZOJ3926】【ZJOI2015】诸神眷顾的幻想乡广义后缀自动机

题目：

思路&做法：

既然只有\(20\)个叶子节点，那么可以从每个叶子节点往上建一颗\(trie\)树, 然后合并成一棵大的\(trie\)树，然后构建广义后缀自动机。

\((\) 实现起来就是dfs时把节点上的颜色加进广义后缀自动机\()\)

再然后就统计一下就可以了\((ans += len[x] - len[fail[x])\)

代码：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

const int N = 2000010;

long long Ans;

struct Suffix_Automaton

{   int nxt[N][10], fail[N], sz;

	int len[N];

	int root;

	Suffix_Automaton() { }

	inline int newnode(int l)

	{   memset(nxt[sz], 0, sizeof(nxt[sz]));

		fail[sz] = 0;

		len[sz] = l;

		return sz++;

	}

	inline void init()

	{   sz = 1;

		root = newnode(0);

	}

	int add(int c, int last)

	{   if(nxt[last][c])

		{	int p = last, q = nxt[p][c];

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

				return q;

			else

			{   int u = newnode(len[p] + 1);

				for(int i=0; i<10; i++) nxt[u][i] = nxt[q][i];

				fail[u] = fail[q];

				fail[q] = u;

				while(nxt[p][c] == q)

				{	nxt[p][c] = u;

					p = fail[p];

				}

				return u;

			}

		}

		else

		{	int now = newnode(len[last] + 1);

			int p = last;

			while(p && !nxt[p][c])

			{	nxt[p][c] = now;

				p = fail[p];

			}

			if(!p) fail[now] = root;

			else

			{   int q = nxt[p][c];

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

					fail[now] = q;

				else

				{   int u = newnode(len[p] + 1);

					for(int i=0; i<10; i++) nxt[u][i] = nxt[q][i];

					fail[u] = fail[q];

					fail[q] = fail[now] = u;

					while(nxt[p][c] == q)

					{   nxt[p][c] = u;

						p = fail[p];

					}

				}

			}

			Ans += (long long) (len[now] - len[fail[now]]);

			return now;

		}

	}

} tzw;

int color[N];

int r[N];

struct edge

{   int from, to;

	edge() { }

	edge(int _1, int _2):from(_1), to(_2) { }

} edges[2*N];

int head[N], nxt[2*N], tot;

inline void init()

{   memset(head, -1, sizeof(head));

	tot = 0;

}

inline void Add_Edge(int x, int y)

{   edges[tot] = edge(x, y);

	nxt[tot] = head[x];

	head[x] = tot++;

	edges[tot] = edge(y, x);

	nxt[tot] = head[y];

	head[y] = tot++;

}

void dfs(int x, int fa, int last)

{   last = tzw.add(color[x], last);

	for(int i=head[x]; ~i; i=nxt[i])

	{   edge & e = edges[i];

		if(e.to != fa)

			dfs(e.to, x, last);

	}

}

int main()

{   int n, m;

	scanf("%d %d", &n, &m);

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

		scanf("%d", &color[i]);

	tzw.init();

	init();

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

	{   int x, y;

		scanf("%d %d", &x, &y);

		Add_Edge(x, y);

		r[x]++, r[y]++;

	}

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

		if(r[i] == 1) dfs(i, 0, tzw.root);

	printf("%lld\n", Ans);

	return 0;

}

巴特西

【BZOJ3926】【ZJOI2015】诸神眷顾的幻想乡广义后缀自动机

题目：

思路&做法：

代码：

最新文章

热门文章

巴特西

【BZOJ3926】【ZJOI2015】诸神眷顾的幻想乡 广义后缀自动机

题目：

思路&做法：

代码：

最新文章

热门文章

【BZOJ3926】【ZJOI2015】诸神眷顾的幻想乡广义后缀自动机