题目链接：

---

 

广义后缀自动机...

久仰公之大名啊...

太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过$20$个。 

这就是说叶子节点的个数不超过$20$个，我们知道树上的每一条路径一定对应了一个:以某一个叶子节点为根的tire树的后缀的前缀(也就是子串),我们知道SAM是可以统计不同子串的个数的即：${\sum _{i=1}^{n} (len[i]-len[fa[i]])}$

考虑如何把这20棵tire构成一个后缀自动机，我们在只有一个串的时候$np$就是直接指向前一个字符的位置，因为我们现在是树结构，所以$np$指向的应该是该点在$trie$树中父节点的位置，其他的就和普通的$SAM$一样，为了找到节点的父亲，$DFS$找即可。

---

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 100001010 #define llg long long11 #define SIZE 11 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);13 llg n,m,last=1,root=1,du[maxn],v[maxn];14 15 vector
            
             a[maxn];16 17 struct SAM18 {19 struct20 {21 llg len,f,ch[SIZE];22 void init(){len=0,f=0,memset(ch,0,sizeof(ch));}23 }e[maxn*2];24 25 llg insert(llg p,llg c)26 {27 llg np=++last; e[np].init(); 28 e[np].len=e[p].len+1;29 for (;p && !e[p].ch[c];p=e[p].f) e[p].ch[c]=np;30 if (!p) e[np].f=root;31 else32 {33 llg q=e[p].ch[c];34 if (e[q].len==e[p].len+1) e[np].f=q;35 else36 {37 llg nq=++last;38 e[nq].init();39 e[nq]=e[q];40 e[nq].len=e[p].len+1;41 e[q].f=e[np].f=nq;42 for (;p && e[p].ch[c]==q;p=e[p].f) e[p].ch[c]=nq;43 }44 }45 return np;46 }47 }sam;48 49 void init()50 {51 llg x,y;52 cin>>n>>m;53 for (llg i=1;i<=n;i++) scanf("%lld",&v[i]);54 for (llg i=1;i