P3346 [ZJOI2015]诸神眷顾的幻想乡 题解
题面
把所有叶子拎起来当根，合并成一棵trie之后建广义 SAM（我直接每个叶子直接跑的，每次 \(lastpos\) 重置，也可过）。
点击查看代码
const int N=1e5+13,M=2e6+13;
int n,m,nxt[M<<1],len[M<<1],ptot=1;
std::vector son[M<<1],zrzak;
inline void clear(){son[1].resize(m),zrzak.resize(m);}
inline int newpos(std::vector nson,int nlen){return len[++ptot]=nlen,std::swap(son[ptot],nson),ptot;}
inline int insert(int c,int lastpos){
int p=lastpos,u=newpos(zrzak,len[p]+1);
while(p&&!son[p][c]) son[p][c]=u,p=nxt[p];
lastpos=u;
if(!p) return nxt[u]=1,u;
int d=son[p][c];
if(len[d]==len[p]+1) nxt[u]=d;
else{
int v=newpos(son[d],len[p]+1);
nxt[v]=nxt[d],nxt[u]=nxt[d]=v;
while(p&&son[p][c]==d) son[p][c]=v,p=nxt[p];
}
return u;
}
struct Edge{int v,nxt;}e[N<<1];
int a[N],deg[N],h[N],etot,pos[N];
inline void add_edge(int u,int v){e[++etot]=(Edge){v,h[u]};h[u]=etot;}
void dfs(int u,int fa){
pos[u]=insert(a[u],pos[fa]);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa) continue;
dfs(v,u);
}
}
int main(){
read(n),read(m);
clear();
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i