题目概述

有一棵 $n$ 个节点的树，每个节点有一个字符。定义一条路径 $(x,y)$ 形成的字符串为从 $x$ 走到 $y$ 路径上所有字符按顺序接起来形成的字符串。求所有本质不同的字符串。叶子节点个数不超过 $20$ 。

解题报告

ZJOI听课掉线？不如临时抱佛脚！

因为所有形成的字符串都是两个叶子节点之间的路径的子串，所以我们可以从每个叶子出发构造一棵Trie，把这些Trie合并成一棵大Trie，然后求这棵大Trie中有多少本质不同的子串。

求本质不同的子串可以用SAM，但是树上SAM是什么鬼啊？？？

广义SAM，记录下每个点的停留节点，每次加入节点的时候从上一次的停留节点开始，检查待添加节点是否存在，如果存在的话就不需要新建节点，只需要新建辅助节点，否则就正常插入。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,maxt=4000000,maxc=10;

int n,m,c[maxn+5],D[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

namespace SAM{
    int len=1,ro=1,son[maxt+5][maxc],fa[maxt+5],MAX[maxt+5];
    inline int Extend(int p,int c){
        if (son[p][c]){
            int q=son[p][c];if (MAX[p]+1==MAX[q]) return q;
            int nq=++len;MAX[nq]=MAX[p]+1;for (int i=0;i<m;i++) son[nq][i]=son[q][i];
            fa[nq]=fa[q];fa[q]=nq;while (p&&son[p][c]==q) son[p][c]=nq,p=fa[p];return nq;
        } else{
            int np=++len;MAX[np]=MAX[p]+1;while (p&&!son[p][c]) son[p][c]=np,p=fa[p];
            if (!p) return fa[np]=ro,np;int q=son[p][c];if (MAX[p]+1==MAX[q]) return fa[np]=q,np;
            int nq=++len;MAX[nq]=MAX[p]+1;for (int i=0;i<m;i++) son[nq][i]=son[q][i];
            fa[nq]=fa[q];fa[q]=fa[np]=nq;while (p&&son[p][c]==q) son[p][c]=nq,p=fa[p];return np;
        }
    }
    inline LL Count() {LL sum=0;for (int i=1;i<=len;i++) sum+=MAX[i]-MAX[fa[i]];return sum;}
}
#define Add(x,y) (son[++E]=(y),D[x]++,nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int lst,int pre=0){
    int now=SAM::Extend(lst,c[x]);
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],now,x);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&c[i]);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    for (int i=1;i<=n;i++) if (D[i]==1) Dfs(i,1);printf("%lld\n",SAM::Count());return 0;
}