---

考虑怎么样才能构造出匹配所有字符的后缀自动机

发现显然问题出在树上分叉处，需要分别对几个儿子构造

而方向不同会导致问题

但是这道题保证叶子结点不到$20$个

从每个叶子节点开始$dfs$一次，对所有串建一个广义$Sam$即可

注意构建方式，每个儿子继承父亲的$last$

而$Sam$上一个点对应子串个数就是$len[i]-len[fa[i]]$

#include
    
     using namespace std;const int RLEN=1<<21|1;inline char gc(){
        static char ibuf[RLEN],*ib,*ob;    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));    return (ib==ob)?EOF:*ib++;} #define gc getcharinline int read(){
        char ch=gc();    int res=0,f=1;    while(!isdigit(ch))f^=ch=='-',ch=gc();    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();    return f?res:-res;}#define ll long long#define pii pair
     
      #define fi first#define se second#define pb push_back#define pob pop_back#define pf push_front#define pof pop_front#define mp make_pair#define bg begin#define re registerconst int N=4000005;int nxt[N][12],len[N],fa[N],tot;inline int insert(int c,int last){
        int cur=++tot,p=last;len[cur]=len[p]+1;    for(;p&&!nxt[p][c];p=fa[p])nxt[p][c]=cur;    if(!p)fa[cur]=1;    else{
            int q=nxt[p][c];        if(len[p]+1==len[q])fa[cur]=q;        else {
                int clo=++tot;            memcpy(nxt[clo],nxt[q],sizeof(nxt[q]));            fa[clo]=fa[q],len[clo]=len[p]+1;            fa[q]=fa[cur]=clo;            for(;p&&nxt[p][c]==q;p=fa[p])nxt[p][c]=clo;        }    }return cur;}const int M=200005;int n,c;int in[M],val[M];vector
      
       e[M];void dfs(int u,int f,int last){
        int p=insert(val[u],last);    for(int i=0;i