bzoj Luogu https://www.luogu.com.cn/problem/P3346
题解时间
给你个无根 trie 树 (你管这叫 trie 树?), 问你选取一条有向路径能形成多少种不同字符串.
太阳花田的结构比较特殊, 只与一个空地相邻的空地数量不超过 20 个.-> 只有不超过 20 个叶子.
纯粹看你读题的, 你要是读错了这句话的含义你就白给.
如何保证完整枚举这棵树上所有可能的字符串呢?
我们以某个点为根建广义 SAM, 很明显每一个点都只有向根方向延展出的字符串没有被记入了 SAM 中.
而对于一个叶子节点, 只有以它为根建 SAM 时, 以它为起点延展出的字符串才会被记录.
而对于一个非叶子节点, 很明显一定有两个叶子节点在它的不同方向.
所以只需要对于每个叶子节点为根建广义 SAM 放在一起进行统计即可.
本质不同字符串个数为 $ \Sigma len[x]-len[pre[x]] $ .
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long lint;
- namespace RKK
- {
- const int N=200011,L=30;
- struct yuuka{int to,ne;}e[N];int he[N],ecnt,ind[N];
- void addline(int f,int t)
- {
- e[++ecnt].to=t;
- e[ecnt].ne=he[f];
- he[f]=ecnt;
- ind[t]++;
- }
- int n,str[N];
- lint ans;
- struct remilia{int tranc[10],len,pre;};
- struct sakuya
- {
- remilia s[N*20];
- int fin,size;
- sakuya(){fin=size=1;}
- void ins(int ch)
- {
- int npx,npy,lpx,lpy;
- if(s[fin].tranc[ch])
- {
- lpy=s[fin].tranc[ch],lpx=fin;
- if(s[lpy].len==s[lpx].len+1) fin=lpy;
- else
- {
- npy=++size;
- s[npy]=s[lpy];
- s[npy].len=s[lpx].len+1;
- s[lpy].pre=npy;
- while(s[lpx].tranc[ch]==lpy)
- {
- s[lpx].tranc[ch]=npy;
- lpx=s[lpx].pre;
- }
- fin=npy;
- }
- return;
- }
- npx=++size;
- s[npx].len=s[fin].len+1;
- for(lpx=fin;lpx&&!s[lpx].tranc[ch];lpx=s[lpx].pre) s[lpx].tranc[ch]=npx;
- if(!lpx) s[npx].pre=1;
- else
- {
- lpy=s[lpx].tranc[ch];
- if(s[lpy].len==s[lpx].len+1) s[npx].pre=lpy;
- else
- {
- npy=++size;
- s[npy]=s[lpy];
- s[npy].len=s[lpx].len+1;
- s[npx].pre=s[lpy].pre=npy;
- while(s[lpx].tranc[ch]==lpy)
- {
- s[lpx].tranc[ch]=npy;
- lpx=s[lpx].pre;
- }
- }
- }
- fin=npx;
- }
- void work(){for(int i=2;i<=size;i++) ans+=s[i].len-s[s[i].pre].len;}
- }sam;
- void dfs(int x,int f,int fi)
- {
- sam.fin=fi,sam.ins(str[x]);
- int fl=sam.fin;
- for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(t!=f)
- dfs(t,x,fl);
- }
- int Iris()
- {
- scanf("%d%*d",&n);
- for(int i=1;i<=n;i++) scanf("%d",&str[i]);
- for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),addline(x,y),addline(y,x);
- for(int i=1;i<=n;i++)if(ind[i]==1) dfs(i,0,1);
- sam.work();
- printf("%lld\n",ans);
- return 0;
- }
- }
- int main(){return RKK::Iris();}
来源: http://www.bubuko.com/infodetail-3344036.html