自动搬运

查看原文

来自洛谷，原作者为

	辰星凌 时过而不知泪已落 —散华礼弥

搬运于2025-08-24 21:47:57，当前版本为作者最后更新于2019-12-14 10:42:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（本文已被阉割，原文 广义 $\text{SAM}$ 详解 进行增修后转到了模板题处）

传送门：诸神眷顾的幻想乡 $\text{[ZJOI2015] [P3346]}$ $\text{[Bzoj3926]}$

【题目描述】

给出一颗叶子结点不超过 $20$ 个的无根树，每个节点上都有一个不超过 $10$ 的数字，求树上本质不同的路径个数（两条路径相同定义为：其路径上所有节点上的数字依次相连组成的字符串相同）。

【分析】

首先有一个很麻烦的地方是路径可以拐弯（即两端点分别在其 $lca$ 两个不同儿子节点的子树中），而 $\text{Trie}$ 树和各种自动机在“接受”字符串时都是以根为起点从上往下径直走到底（什么？跳 $parent$ 树？你跳任你跳，跳完还是直的）

所以要想办法把路径捋直，瞎 $yy$ 可能不太容易想出来，这里直接抛结论：

一颗无根树上任意一条路径必定可以在以某个叶节点为根时，变成一条从上到下的路径（利于广义 $\text{SAM}$ 的使用）。

注意到题目中说叶节点不超过 $20$ 个，这意味着什么？

暴力枚举每一个叶节点作为根节点遍历整棵树啊！

将一共 $cnt_{leaf}$ 颗树中的所有前缀串都抽出来建立广义 $\text{SAM}$，然后直接求本质不同的子串个数。 其中前缀串定义为从根节点（无根树的某个叶子结点）到任意一个节点的路径所构成的字符串（实际上就是将 $cnt_{leaf}$ 颗 $\text{Trie}$ 树合在了一起跑广义 $\text{SAM}$）。

注意数组大小和空间限制。

【Code (离线)】

（本题 $\text{Trie}$ 树的构造方法与其他相比较为特别）

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=4e6+5,N20=2e6+3,Nn=1e5+3;
int n,m,o,x,y,t,C,du[Nn],co[Nn],head[Nn];LL ans;
struct QAQ{int to,next;}a[Nn<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Trie{
    int O,c[N20],fa[N20],tr[N20][10];
    Trie(){O=1;}
    inline int insert(Re p,Re ch){//在p后面插入一个ch
        if(!tr[p][ch])tr[p][ch]=++O,c[O]=ch,fa[O]=p;
        return tr[p][ch];
    }
}T1;
struct Suffix_Automaton{    
    int O,pos[N],link[N],trans[N][10],maxlen[N];queue<int>Q;
    Suffix_Automaton(){O=1;}
    inline int insert(Re ch,Re last){
        Re x,y,z=++O,p=last;maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<C;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        return z;
    }
    inline void build(){ 
        for(Re i=0;i<C;++i)if(T1.tr[1][i])Q.push(T1.tr[1][i]);
        pos[1]=1;
        while(!Q.empty()){
            Re x=Q.front();Q.pop();
            pos[x]=insert(T1.c[x],pos[T1.fa[x]]);
            for(Re i=0;i<C;++i)if(T1.tr[x][i])Q.push(T1.tr[x][i]);
        }
    }
    inline void sakura(){
        for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
        printf("%lld\n",ans); 
    }
}SAM;
inline void dfs(Re x,Re fa,Re fap){//遍历构造Trie树 
    Re xp=T1.insert(fap,co[x]);//记录在Trie树上的位置，方便下次直接使用
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa)dfs(to,x,xp);
}
int main(){
//  freopen("123.txt","r",stdin);
    in(n),in(C),m=n-1;
    for(Re i=1;i<=n;++i)in(co[i]);
    while(m--)in(x),in(y),add(x,y),add(y,x),++du[x],++du[y];
    for(Re i=1;i<=n;++i)if(du[i]==1)dfs(i,0,1);//依次把每个叶子节点作为根插入Trie树
    SAM.build(),SAM.sakura();
}

【Code (在线)】

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=4e6+5,N20=2e6+3,Nn=1e5+3;
int n,m,o,x,y,t,C,du[Nn],co[Nn],head[Nn];LL ans;
struct QAQ{int to,next;}a[Nn<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Suffix_Automaton{
    int O,link[N],trans[N][10],maxlen[N];
    Suffix_Automaton(){O=1;}
    inline int insert(Re ch,Re last){
        if(trans[last][ch]){
            Re p=last,x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])return x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<10;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[x]=y;
                return y;
            }
        }
        Re z=++O,p=last;maxlen[z]=maxlen[last]+1;
        while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];
        if(!p)link[z]=1;
        else{
            Re x=trans[p][ch];
            if(maxlen[p]+1==maxlen[x])link[z]=x;
            else{
                Re y=++O;maxlen[y]=maxlen[p]+1;
                for(Re i=0;i<10;++i)trans[y][i]=trans[x][i];
                while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];
                link[y]=link[x],link[z]=link[x]=y;
            }
        }
        return z;
    }
    inline void sakura(){
        for(Re i=2;i<=O;++i)ans+=maxlen[i]-maxlen[link[i]];
        printf("%lld\n",ans); 
    }
}SAM;
inline void dfs(Re x,Re fa,Re fap){//遍历在线构造SAM
    Re xp=SAM.insert(co[x],fap);//记录x在SAM上的位置，方便下次直接使用
    for(Re i=head[x],to;i;i=a[i].next)
        if((to=a[i].to)!=fa)dfs(to,x,xp);
}
int main(){
//  freopen("123.txt","r",stdin);
    in(n),in(C),m=n-1;
    for(Re i=1;i<=n;++i)in(co[i]);
    while(m--)in(x),in(y),add(x,y),add(y,x),++du[x],++du[y];
    for(Re i=1;i<=n;++i)if(du[i]==1)dfs(i,0,1);//依次把每个叶子节点作为根插入Trie树
    SAM.sakura();
}