P3346 [ZJOI2015]诸神眷顾的幻想乡

## $\text{Solution}$ 话说这种通过对树的形态特殊限制最近做了还有[一道](https://www.luogu.com.cn/problem/P3241)，以保证暴力做法复杂度。 链怎么做？是不是从上至下以及从下到上类似于 trie 的形式建广义 SAM 求不同子串。或者你思考现在只有一段序列，不同子串的求法，用 SAM 就好，那么正反都要，是不是我正向跑一次，反向跑一次，但这时候就要用到广义 SAM 了，然后这种正向依赖前一个字符的序列做法实际上就是链上依赖 trie 树的上一个字符。？ 抽象的，我们只是把每一个前缀插入到 SAM 里面了，那么获取这些前缀的方法，我们可以类似于 trie ，但实际上 dfs 保证依赖关系就好了。  类比到树上：看图下，摸了几遍发现，假如我们要保证正序和倒序的字符串都能被找到，那么我们必须要从叶子节点出发，仿照链的做法即可。 注意下广义 SAM 的 $pre$ 以及空间问题。 ## $\text{Code}$ ```cpp #include <bits/stdc++.h> #define N (int)(2e6+5) #define ll long long using namespace std; struct edge { int nex,to; }e[N]; int head[N],cnt; int du[N],col[N],fa[N],son[10][N],len[N]; int n,m,tot=1; int rd() { int f=1,sum=0; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return sum*f; } void add_edge(int x,int y) { e[++cnt].nex=head[x]; e[cnt].to=y; head[x]=cnt; } int ins(int c,int las) { if(son[c][las]) { int pre=las,y=son[c][las]; if(len[pre]+1==len[y]) return y; int x=++tot; len[x]=len[pre]+1; fa[x]=fa[y]; fa[y]=x; for(int i=0;i<10;i++) son[i][x]=son[i][y]; for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=x; return x; } int pre=las,x=++tot; len[x]=len[pre]+1; for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x; int y=son[c][pre]; if(!pre) fa[x]=1; else if(len[pre]+1==len[y]) fa[x]=y; else { int p=++tot; len[p]=len[pre]+1; fa[p]=fa[y]; fa[x]=fa[y]=p; for(int i=0;i<10;i++) son[i][p]=son[i][y]; for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p; } return x; } void dfs(int x,int fa,int las) { las=ins(col[x],las); for(int i=head[x];i;i=e[i].nex) { int y=e[i].to; if(y==fa) continue; dfs(y,x,las); } } int main() { int x,y; n=rd(); m=rd(); for(int i=1;i<=n;i++) col[i]=rd(); for(int i=1;i<n;i++) { x=rd(); y=rd(); add_edge(x,y); add_edge(y,x); ++du[x]; ++du[y]; } for(int i=1;i<=n;i++) if(du[i]==1) dfs(i,0,1); ll ans=0; for(int i=2;i<=tot;i++) ans+=len[i]-len[fa[i]]; printf("%lld",ans); return 0; } ```