bzoj3926/luoguP3346 [Zjoi2015]诸神眷顾的幻想乡(trie上构建广义后缀自动机)

bzoj Luogu

题解时间

给你个无根trie树(你管这叫trie树？)，问你选取一条有向路径能形成多少种不同字符串。

太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过20个。->只有不超过20个叶子。

纯粹看你读题的，你要是读错了这句话的含义你就白给。

如何保证完整枚举这棵树上所有可能的字符串呢？

我们以某个点为根建广义SAM，很明显每一个点都只有向根方向延展出的字符串没有被记入了SAM中。

而对于一个叶子节点，只有以它为根建SAM时，以它为起点延展出的字符串才会被记录。

而对于一个非叶子节点，很明显一定有两个叶子节点在它的不同方向。

所以只需要对于每个叶子节点为根建广义SAM放在一起进行统计即可。

本质不同字符串个数为 $ \Sigma len[x]-len[pre[x]] $ 。

#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

namespace RKK

{

const int N=200011,L=30;

struct yuuka{int to,ne;}e[N];int he[N],ecnt,ind[N];

void addline(int f,int t)

{

	e[++ecnt].to=t;

	e[ecnt].ne=he[f];

	he[f]=ecnt;

	ind[t]++;

}

int n,str[N];

lint ans;

struct remilia{int tranc[10],len,pre;};

struct sakuya

{

	remilia s[N*20];

	int fin,size;

	sakuya(){fin=size=1;}

	void ins(int ch)

	{

		int npx,npy,lpx,lpy;

		if(s[fin].tranc[ch])

		{

			lpy=s[fin].tranc[ch],lpx=fin;

			if(s[lpy].len==s[lpx].len+1) fin=lpy;

			else

			{

				npy=++size;

				s[npy]=s[lpy];

				s[npy].len=s[lpx].len+1;

				s[lpy].pre=npy;

				while(s[lpx].tranc[ch]==lpy)

				{

					s[lpx].tranc[ch]=npy;

					lpx=s[lpx].pre;

				}

				fin=npy;

			}

			return;

		}

		npx=++size;

		s[npx].len=s[fin].len+1;

		for(lpx=fin;lpx&&!s[lpx].tranc[ch];lpx=s[lpx].pre) s[lpx].tranc[ch]=npx;

		if(!lpx) s[npx].pre=1;

		else

		{

			lpy=s[lpx].tranc[ch];

			if(s[lpy].len==s[lpx].len+1) s[npx].pre=lpy;

			else

			{

				npy=++size;

				s[npy]=s[lpy];

				s[npy].len=s[lpx].len+1;

				s[npx].pre=s[lpy].pre=npy;

				while(s[lpx].tranc[ch]==lpy)

				{

					s[lpx].tranc[ch]=npy;

					lpx=s[lpx].pre;

				}

			}

		}

		fin=npx;

	}

	void work(){for(int i=2;i<=size;i++) ans+=s[i].len-s[s[i].pre].len;}

}sam;

void dfs(int x,int f,int fi)

{

	sam.fin=fi,sam.ins(str[x]);

	int fl=sam.fin;

	for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(t!=f)

		dfs(t,x,fl);

}

int Iris()

{

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

	for(int i=1;i<=n;i++) scanf("%d",&str[i]);

	for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),addline(x,y),addline(y,x);

	for(int i=1;i<=n;i++)if(ind[i]==1) dfs(i,0,1);

	sam.work();

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

	return 0;

}

}

int main(){return RKK::Iris();}

巴特西

bzoj3926/luoguP3346 [Zjoi2015]诸神眷顾的幻想乡(trie上构建广义后缀自动机)

bzoj3926/luoguP3346 [Zjoi2015]诸神眷顾的幻想乡(trie上构建广义后缀自动机)

题解时间

最新文章

热门文章