luoguP3346 [ZJOI2015]诸神眷顾的幻想乡

题意

学习了广义后缀自动机。

广义后缀自动机与普通后缀自动机的区别在于它是对多个串建的，于是可以处理多个串。

广义后缀自动机和普通后缀自动机的区别在于两个特判，可以见这篇题解

对于这题，因为叶子数量小于20，以每个叶子为根跑dfs，将跑到的字符串插入SAM即可，求不同子串个数是SAM的常规操作，见我的笔记。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2000010;

const int maxc=15;

int n,C,cnt;

int head[maxn],a[maxn],in[maxn];

struct edge{int to,nxt;}e[maxn<<1];

struct SAM

{

	int tot,last;

	int fa[maxn<<1],len[maxn<<1];

	int ch[maxn<<1][maxc];

	SAM(){last=tot=1;}

	inline void add(int c)

	{

		if(ch[last][c]&&len[ch[last][c]]==len[last]+1){last=ch[last][c];return;}

		int now=++tot;len[now]=len[last]+1;

		int p=last;

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

		if(!p){fa[now]=1;last=now;return;}

		int q=ch[p][c];

		bool flag=0;

		if(len[q]==len[p]+1)fa[now]=q;

		else

		{

			if(p==last)flag=1;

			int nowq=++tot;len[nowq]=len[p]+1;

			for(int i=0;i<C;i++)ch[nowq][i]=ch[q][i];

			fa[nowq]=fa[q],fa[q]=fa[now]=nowq;

			while(p&&ch[p][c]==q)ch[p][c]=nowq,p=fa[p];

			if(flag)last=nowq;

		}

		if(!flag)last=now;

	}

	inline ll query()

	{

		ll res=0;

		for(int i=2;i<=tot;i++)res+=len[i]-len[fa[i]];

		return res;

	}

}sam;

inline void add(int u,int v)

{

	e[++cnt].nxt=head[u];

	head[u]=cnt;

	e[cnt].to=v;

	in[v]++;

}

void dfs(int x,int fa)

{

	sam.add(a[x]);int last=sam.last;

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

	{

		int y=e[i].to;

		if(y==fa)continue;

		sam.last=last;dfs(y,x);

	}

}

int main()

{

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

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

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

	{

		int u,v;scanf("%d%d",&u,&v);

		add(u,v),add(v,u);

	}

	for(int i=1;i<=n;i++)if(in[i]==1)sam.last=1,dfs(i,0);

	//cerr<<sam.tot<<endl;

	printf("%lld",sam.query());

	return 0;

}

巴特西

luoguP3346 [ZJOI2015]诸神眷顾的幻想乡

题意

最新文章

热门文章