bzoj 3926: 诸神眷顾的幻想乡 广义后缀自动机

题目:

题解:

我们发现很关键的一点 : 只与一个空地相邻的空地数量不超过20个

也就是说叶子节点最多有20个

所以我们想到了将所有的串提取出来的方法:

分别以每个叶子为根,用所有的树共同建立广义后缀自动机

然后直接统计所有的\(len_x - len_{fa_x}\)即可

其实这是论文题:

见:

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 100010;

struct Edge{

	int to,next;

}G[maxn<<1];

int head[maxn],cnt,maxc;

void add(int u,int v){

	G[++cnt].to = v;

	G[cnt].next = head[u];

	head[u] = cnt;

}

int w[maxn],deg[maxn];

struct Node{

	int nx[10];

	int len,fa;

}T[maxn*20*2];

int nodecnt;

inline int insert(int last,int c){

	int cur = ++nodecnt,p;

	T[cur].len = T[last].len + 1;

	for(p = last;p != -1 && !T[p].nx[c];p = T[p].fa) T[p].nx[c] = cur;

	if(p == -1) T[p].fa = 0;

	else{

		int q = T[p].nx[c];

		if(T[q].len == T[p].len + 1) T[cur].fa =q;

		else{

			int co = ++ nodecnt;

			T[co] = T[q];T[co].len = T[p].len + 1;

			for(;p != -1 && T[p].nx[c] == q;p = T[p].fa) T[p].nx[c] = co;

			T[cur].fa = T[q].fa = co;

		}

	}return cur;

}

#define v G[i].to

void dfs(int u,int fa,int last){

	last = insert(last,w[u]);

	for(int i = head[u];i;i=G[i].next){

		if(v == fa) continue;

		dfs(v,u,last);

	}

}

#undef v

inline void init(){

	nodecnt = 0;

	T[0].fa = -1;

}

int main(){

	init();int n;read(n);read(maxc);

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

	for(int i=1,u,v;i<n;++i){

		read(u);read(v);

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

		++deg[u];++deg[v];

	}

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

		if(deg[i] == 1) dfs(i,0,0);

	}ll ans = 0;

	for(int i=1;i<=nodecnt;++i){

		ans += (T[i].len - T[T[i].fa].len);

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

	getchar();getchar();

	return 0;

}