題意：給一棵 $n$ 個點的樹，每個點有個字符，另給一個長度為 $m$ 的特征串，求樹上 $n^2$ 條有向路徑在特征串中出現的次數之和。

$n,m\le 5\times 10^4$

看到母串先建 SAM （bushi

樹上路徑統計問題，考慮點分治。

對當前分治中心，我們希望求出所有經過分治中心的路徑的貢獻。因為是計數問題，同一個子樹的可以容斥掉，所以這不會成為思維瓶頸。

考慮求出特征串上每個位置作為分治中心的匹配點的方案數，我們只需要求出這個位置結束的后綴以及開始的前綴總共可以匹配多少個以分治中心為終點或起點的路徑。兩個是同理的，考慮前面一個。

我們然后從分治中心開始 dfs，記錄從當前點到分治中心的路徑構成的串在 SAM 上的位置。如果這個串不是其等價類中最長的，那么判斷一下加入一個字符后是否是等價類中長度多 $1$ 的串，不是就返回。

如果是等價類中最長的，前面加一個字符后可（yi）能（ding）會對應多個狀態。在 SAM 上預處理出一個 $nxt(p,c)$，表示 $p$ 號結點代表的最長串在前面加上字符 $c$ 后到達的狀態，沒有為 $0$。每訪問一個位置就讓該結點的計數器 $+1$。

然后我們要求某個位置結尾的后綴被訪問次數之和，也就是到根的路徑和，做一個樹上前綴和即可。

這樣對一個大小為 $siz$ 的連通塊復雜度是 $\mathrm{O}(siz+m)$，在 $siz$ 很小時顯得浪費。

考慮根號分治，當 $siz<\sqrt{n}$ 時直接 $\mathrm{O}(si{z}^2)$ 暴力。這樣點分治只會遞歸一半的層數，暴力的次數也只有 $\mathrm{O}(\sqrt{n})$。總復雜度 $\mathrm{O}((n+m)\sqrt{n})$

注意容斥的時候也要根號分治，否則會被菊花圖卡。

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <cmath> #define MAXN 100005 using namespace std; typedef long long ll; int n,m,B; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } struct SAM {char s[MAXN];int ch[MAXN][26],nxt[MAXN][26],fa[MAXN],len[MAXN],pos[MAXN],rt[MAXN],sum[MAXN],siz[MAXN],tot,las;void insert(int c,int k){int cur=++tot,p=las;len[cur]=len[p]+1;for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;if (!p) fa[cur]=1;else{int q=ch[p][c];if (len[q]==len[p]+1) fa[cur]=q;else{int _q=++tot;len[_q]=len[p]+1;fa[_q]=fa[q],fa[q]=fa[cur]=_q;memcpy(ch[_q],ch[q],sizeof(ch[q]));for (;ch[p][c]==q;p=fa[p]) ch[p][c]=_q; } } ++siz[pos[k]=las=cur];}int a[MAXN],c[MAXN];void build(){tot=las=1;for (int i=1;i<=m;i++) insert(s[i]-'a',i);for (int i=1;i<=tot;i++) ++c[len[i]];for (int i=1;i<=tot;i++) c[i]+=c[i-1];for (int i=1;i<=tot;i++) a[c[len[i]]--]=i;for (int i=1;i<=m;i++) rt[pos[i]]=i;for (int i=tot;i>=1;i--) rt[fa[a[i]]]=rt[a[i]],siz[fa[a[i]]]+=siz[a[i]];for (int i=2;i<=tot;i++) nxt[fa[i]][s[rt[i]-len[fa[i]]]-'a']=i;}int getnxt(int p,int l,int c){if (l<len[p]) return c==s[rt[p]-l]-'a'? (++sum[p],p):0;return ++sum[p=nxt[p][c]],p;}inline void clear(){for (int i=1;i<=tot;i++) sum[i]=0;}inline void getsum(int* ans){for (int i=2;i<=tot;i++) sum[a[i]]+=sum[fa[a[i]]];for (int i=1;i<=m;i++) ans[i]=sum[pos[i]];} }S,T; ll ans; vector<int> e[MAXN]; char s[MAXN]; int vis[MAXN],fa[MAXN]; int siz[MAXN],maxp[MAXN],rt; void findrt(int u,int f,int sum) {siz[u]=1,maxp[u]=0;for (int i=0;i<(int)e[u].size();i++)if (!vis[e[u][i]]&&e[u][i]!=f){findrt(e[u][i],u,sum);siz[u]+=siz[e[u][i]];maxp[u]=max(maxp[u],siz[e[u][i]]);}maxp[u]=max(maxp[u],sum-siz[u]);if (maxp[u]<maxp[rt]) rt=u; } void dfs(SAM& S,int u,int f,int l,int p) {siz[u]=1,p=S.getnxt(p,l,s[u]-'a');for (int i=0;i<(int)e[u].size();i++)if (!vis[e[u][i]]&&e[u][i]!=f)dfs(S,e[u][i],u,l+1,p),siz[u]+=siz[e[u][i]]; } vector<int> lis; void dfs(int u,int f) {lis.push_back(u),fa[u]=f;for (int i=0;i<(int)e[u].size();i++)if (!vis[e[u][i]]&&e[u][i]!=f)dfs(e[u][i],u); } void dfs(int u,int f,int p,int v) {if (!(p=S.ch[p][s[u]-'a'])) return;ans+=v*S.siz[p];for (int i=0;i<(int)e[u].size();i++)if (!vis[e[u][i]]&&e[u][i]!=f)dfs(e[u][i],u,p,v); } int a[MAXN],b[MAXN]; void calc() {S.clear(),T.clear();dfs(S,rt,0,0,1),dfs(T,rt,0,0,1);S.getsum(a),T.getsum(b);for (int i=1;i<=m;i++) ans+=(ll)a[i]*b[m-i+1];for (int i=0;i<(int)e[rt].size();i++)if (!vis[e[rt][i]]){if (siz[e[rt][i]]<B){lis.clear(),dfs(e[rt][i],rt);for (int j=0;j<(int)lis.size();j++){int v=lis[j],p=1;while (fa[v]) p=S.ch[p][s[v]-'a'],v=fa[v];p=S.ch[p][s[rt]-'a'];dfs(e[rt][i],0,p,-1);}}else{S.clear(),T.clear();dfs(S,e[rt][i],0,1,S.ch[1][s[rt]-'a']),dfs(T,e[rt][i],0,1,T.ch[1][s[rt]-'a']);S.getsum(a),T.getsum(b);for (int i=1;i<=m;i++) ans-=(ll)a[i]*b[m-i+1];}} } void calcV() {lis.clear(),dfs(rt,0);for (int i=0;i<(int)lis.size();i++) dfs(lis[i],0,1,1); } void solve() {int u=rt;vis[u]=1;calc();for (int i=0;i<(int)e[u].size();i++)if (!vis[e[u][i]]){rt=0,findrt(e[u][i],0,siz[e[u][i]]);siz[e[u][i]]<B? calcV():solve();} } int main() {maxp[0]=0x7fffffff;B=sqrt(n=read()),m=read();for (int i=1;i<n;i++){int u,v;u=read(),v=read();e[u].push_back(v),e[v].push_back(u);}scanf("%s",s+1);scanf("%s",S.s+1);for (int i=1;i<=m;i++) T.s[m-i+1]=S.s[i];S.build(),T.build();findrt(1,0,n);solve();cout<<ans<<'\n';return 0; }

總結

以上是生活随笔為你收集整理的【CTSC2010】珠宝商【后缀自动机】【点分治】【根号分治】的全部內容，希望文章能夠幫你解決所遇到的問題。

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