首先一个串的不同子串和就是sam所有的st[i]-st[fail[i]]之和。 这题以每个叶子结点为根，dfs建立广义sam就好了。。（其实学过sam还是蛮简单的吧吧吧） （去年写的，代码似乎不忍直视？）
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #define ll long long #define gc getchar() #define N 100009 #define M 4000009 using namespace std; int num=0,first[N],n,m,v[N],du[N]; ll ans; struct edge { int next,to; void add(int x,int y) { to=y,next=first[x],first[x]=num; } }e[N*2]; struct sam { int fail[M],st[M],son[M][10],cnt; void csh() { cnt=1; } int extend(int p,int c) { int np=++cnt; st[np]=st[p]+1; while (!son[p][c]&&p) son[p][c]=np,p=fail[p]; if (!p) fail[np]=1; else { int q=son[p][c]; if (st[q]==st[p]+1) fail[np]=q; else { int nq=++cnt; st[nq]=st[p]+1; memcpy(son[nq],son[q],sizeof(son[q])); fail[nq]=fail[q]; fail[q]=fail[np]=nq; while (son[p][c]==q) son[p][c]=nq,p=fail[p]; } } return np; } void work() { for (int i=1;i<=cnt;i++) ans+=st[i]-st[fail[i]];//st[i]-st[fail[i]] -> different substring number } }Sam; int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-48; while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-48; return s*x; } void dfs(int now,int father,int p) { int temp=Sam.extend(p,v[now]); for (int i=first[now];i;i=e[i].next) if (e[i].to!=father) dfs(e[i].to,now,temp); } int main() { Sam.csh(); n=read(),m=read(); for (int i=1;i<=n;i++) v[i]=read(); for (int i=1;i<n;i++) { int x=read(),y=read(); e[++num].add(x,y),e[++num].add(y,x); du[x]++,du[y]++; } for (int i=1;i<=n;i++) if (du[i]==1) dfs(i,0,1);//leaf node -> build eneralized sam Sam.work(); printf("%lld\n",ans); return 0; }