正題

題目鏈接:https://www.luogu.com.cn/problem/P3346

---

題目大意

一棵樹，求樹上所有路徑構成的字符串有多少種。（葉子不超過$30$個）

---

解題思路

如果是根節點到一些節點的路徑的話很好做，直接建廣義$SAM$即可，但是因為路徑會拐彎所以我們考慮如何統計拐彎的路徑。

不難發現如果選擇另一個葉子作為根那么就能讓某些拐彎的路徑變直，在每個葉子節點處都跑一遍建立廣義$SAM$即可。

時間復雜度$O(30n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10,M=3e6+10;; struct node{ll to,next; }a[N*2]; ll n,m,tot,ans,w[N],ls[N],in[N]; ll cnt,len[M],fa[M],ch[M][10]; ll Ins(ll c,ll p){if(ch[p][c]){ll q=ch[p][c];if(len[p]+1==len[q])return q;else{ll nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;return nq;}}ll np=++cnt;len[np]=len[p]+1;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;if(!p)fa[np]=1;else{ll q=ch[p][c];if(len[p]+1==len[q])fa[np]=q;else{ll nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[np]=fa[q]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;}}return np; } void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;in[y]++;return; } void dfs(ll x,ll fa,ll last){ll tmp=Ins(w[x],last);for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dfs(y,x,tmp);}return; } int main() {scanf("%lld%lld",&n,&m);cnt=1;for(ll i=1;i<=n;i++)scanf("%lld",&w[i]);for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}for(ll i=1;i<=n;i++)if(in[i]==1)dfs(i,0,1);for(ll i=1;i<=cnt;i++)ans+=len[i]-len[fa[i]];printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P3346-[ZJOI2015]诸神眷顾的幻想乡【广义SAM】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。