广义 SAM 比较简单的题/fad
题意:树上所有路径一共能够组成多少个本质不同子串?
并且数据保证最多只有20个叶子节点。
我们先来考虑一下一种特殊情况:
对于路径 \([u,v]\),\(u\) 是 \(v\) 的父亲或 \(v\) 是 \(u\) 的父亲。
此时做法很明显:将整棵树当做一颗 Trie 树,建立其广义 SAM,然后根据套路求值。
但是很明显这样并不行,因为树并不是一条链。
这题最多只有 20 个叶子节点,暗示我们将每个叶子节点都当做根节点一遍,这样就一定没有考虑漏的情况。
然后就变成广义 SAM 板子题了。。。
code:
#include<cstdio>
#include<queue>
const int M=1e5+5;
int n,m,tot,siz[M],col[M],lst[M*20];
long long ans;
struct Trie{
int chi[11];
}t[M*20];
struct Node{
int chi[11];
int f,len;
}SAM[M*40];
struct Edge{
int to;Edge*nx;
}e[M<<1],*h[M],*cnt=e;
inline void Add(const int&u,const int&v){
*cnt=(Edge){v,h[u]};h[u]=cnt++;
*cnt=(Edge){u,h[v]};h[v]=cnt++;
}
void qwq(int u,int q,int f){
for(Edge*E=h[u];E;E=E->nx){
int v=E->to;
if(v==f)continue;
if(!t[q].chi[col[v]])t[q].chi[col[v]]=++tot;
qwq(v,t[q].chi[col[v]],u);
}
}
void DFS(int u,int f){
if(siz[u]==1){
if(!t[0].chi[col[u]])t[0].chi[col[u]]=++tot;
qwq(u,t[0].chi[col[u]],0);
}
for(Edge*E=h[u];E;E=E->nx){
int v=E->to;
if(v==f)continue;
DFS(v,u);
}
}
inline int Insert(int lst,int s){
int q,p,nq,np;
p=lst;np=++tot;
SAM[np].len=SAM[p].len+1;
for(;p&&!SAM[p].chi[s];p=SAM[p].f)SAM[p].chi[s]=np;
if(!p)SAM[np].f=1;
else{
q=SAM[p].chi[s];
if(SAM[q].len==SAM[p].len+1)SAM[np].f=q;
else{
nq=++tot;
SAM[nq]=SAM[q];
SAM[np].f=SAM[q].f=nq;
SAM[nq].len=SAM[p].len+1;
for(;p&&SAM[p].chi[s]==q;p=SAM[p].f)SAM[p].chi[s]=nq;
}
}
ans+=SAM[np].len-SAM[SAM[np].f].len;
return np;
}
inline void MakeSAM(){
std::queue<int>q;
int u,s;
tot=lst[0]=1;q.push(0);
while(!q.empty()){
u=q.front();q.pop();
for(s=0;s<m;++s){
if(t[u].chi[s]){
lst[t[u].chi[s]]=Insert(lst[u],s);
q.push(t[u].chi[s]);
}
}
}
}
signed main(){
register int i,u,v;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)scanf("%d",col+i);
for(i=1;i<n;++i){
scanf("%d%d",&u,&v);
Add(u,v);++siz[u];++siz[v];
}
DFS(1,0);MakeSAM();
printf("%lld",ans);
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章