BZOJ3926&&lg3346 ZJOI诸神眷顾的幻想乡(广义后缀自动机)

题面

自己找去

HINT

我们可以把题目拆解成几个部分,首先我们手玩一个结论,从所有的叶子节点出发,遍历整颗树,这里面一定包括了所有的文本串,既然如此,就上广义后缀自动机维护,然后本质不同子串个数,也就是\(\sum_{u=2}^{tot}{node[u].len-node[fa].len}\),然后这题就OK了

#include<bits/stdc++.h>
using namespace std;
inline int read(){
int w=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+ch-48;
ch=getchar();
}
return w*f;
}
int n,m,val[2000010];
struct SUFFIXAUTOMATON{
struct Node{
int len,fa;
int ch[20];
}node[2000010];
int lst,tot,root;
inline void init(){
lst=tot=root=1;return;
}
inline void extend(int now){
int p=lst;tot++;lst=tot;int np=tot;
node[np].len=node[p].len+1;
while(p&&!node[p].ch[now]){
node[p].ch[now]=np;
p=node[p].fa;
}
if(!p) node[np].fa=1;
else{
int q=node[p].ch[now];
if(node[q].len==node[p].len+1){
node[np].fa=q;
}
else{
int nq=++tot;node[nq]=node[q];
node[nq].len=node[p].len+1;
node[q].fa=nq;node[np].fa=nq;
while(p&&node[p].ch[now]==q){
node[p].ch[now]=nq;
p=node[p].fa;
}
}
}
}
}SAM;
int cnt,head[2000010],du[2000010];
struct Edge{
int from,to,next;
}edge[4000010];
inline void addedge(int u,int v){
cnt++;
edge[cnt].from=u;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;du[u]++;
}
inline void dfs(int u,int fa){
SAM.extend(val[u]);int cur=SAM.lst;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;if(v==fa) continue;
SAM.lst=cur;dfs(v,u);
}
return;
}
int main(){
n=read();m=read();SAM.init();
for(int i=1;i<=n;i++){
val[i]=read();val[i]++;
}
for(int i=1;i<n;i++){
int x=read();int y=read();
addedge(x,y);addedge(y,x);
}
for(int i=1;i<=n;i++){
if(du[i]!=1) continue;
SAM.lst=1;dfs(i,0);
}
long long ans=0;
for(int i=1;i<=SAM.tot;i++){
int f=SAM.node[i].fa;
ans+=SAM.node[i].len-SAM.node[f].len;
}
cout<<ans<<endl;
return 0;
}
05-11 13:46