题解 P3346 【[ZJOI2015]诸神眷顾的幻想乡】
zcysky
2017-04-14 23:23:01
个人认为ls的题解存在问题。不知道楼上神犇可否有空跟本蒟蒻聊聊此题正解？
这是2015年NOI集训队15人论文题，做法就是在Trie上做后缀自动机。这样的话建立的就是一个广义后缀自动机。
我来简单说下广义后缀自动机的注意点吧：
简单的实现可以每次ins完了之后，将当前指针指回SAM的根节点。
**但是这必须在保证每次加入的串不会相同的情况下才可以实现。否则会导致重复加点的很多问题。**
所以正确的做法是每次加入前判断当前节点在SAM中是否已经存在，再做出判断即可。
详细还请见源代码。
```cpp
// /*[*/#include<stdio.h>//
// #include<stdlib.h>//]++++[->++[->+>++++<<]<][(c)2013]
// #ifndef e//[o
// #include<string.h>//]![misaka.c,size=3808,crc=d0ec3b36][
// #define e 0x1//
// typedef struct{int d,b,o,P;char*q,*p;}f;int p,q,d,b,_=0//|
// #include __FILE__//]>>>[->+>++<<]<[-<<+>>>++<]>>+MISAKA*IMOUTO
// #undef e//[->[-<<+<+<+>>>>]<<<<<++[->>+>>>+<<<<<]>+>+++>+++[>]]b
// #define e(c)/**/if((_!=__LINE__?(_=__LINE__):0)){c;}//[20002,+[-.+]
// ,O,i=0,Q=sizeof(f);static f*P;static FILE*t;static const char*o[]={//
// "\n\40\"8oCan\40not\40open %s\n\0aaFbfeccdeaEbgecbbcda6bcedd#e(bbed$bbd",
// "a6bgcdbbccd#ead$c%bcdea7bccde*b$eebbdda9bsdbeccdbbecdcbbcceed#eaa&bae$cbe",
// "e&cbdd$eldbdeedbbdede)bdcdea&bbde1bedbbcc&b#ccdee&bdcdea'bbcd)e'bad(bae&bccd",
// "e&bbda1bdcdee$bbce#b$c&bdedcd%ecdca4bhcdeebbcd#e$b#ecdcc$bccda7bbcc#e#d%c*bbda",
// ">bad/bbda"};static int S(){return(o[p][q]);}static/**/int/**/Z=0 ;void/**/z(int//
// l){if(/**/Z-l){Z=l;q++;if(p<b*5&&!S()){p+=b;q=0;}}}int main(int I, /**/char**l){//
// d=sizeof(f*);if(1<(O=_)){b=((sizeof(o)/sizeof(char*))-1)/4;q=22; p= 0;while(p<b*5){
// /*<*/if(Z-1){d=S()>96;i=S()-(d?96:32) ;q++;if(p<b*5&&!S()){p+=b; q= 0;}Z=1;}/*[[*/
// while(i){_=o[0][S()-97];I=_-10?b:1; for( ;I--;)putchar(_ );if (! --i||d)z(~i );}
// if(p==b*5&&O){p-=b;O--;}}return 0U; }if(! (P=( f*)calloc /*]*/ (Q ,I)))return 1;
// {;}for(_=p=1;p<I;p++){e(q=1);while (q< p&& strcmp( l[p ] ,l[(q)]))++ q;
// t=stdin;if(q<p){(void)memcpy/* " */ (&P [p],&P [q ] ,Q);continue ;}
//if(strcmp(l[p],"-")){t=fopen(l [ p] ,"rb" ) ;if(!t ){{;} ;
//printf(05+*o,l[p ]);return+1; {;} }}_=b= 1<<16 ;
//*&O=5;do{if(!(P[p].q=realloc (P[p].q,(P[p].P += b)+1))){return 01;}O &=72 /
//6/*][*/;P[p].o+=d=fread(P[p] .q +P[ p ]. o, 1,b,t) ;}//
// while(d==b) ;P [p].q[ P[ p] .o ]= 012;d =0;
// e(fclose(t ) );P [p] .p =P[ p] .q;if (O)
// {for(;d<P[ p] .o ;d= q+ 1) {q= d;
// while(q<P[ p].o&&P[ p].q[q]- 10 ){
// q++;}b=q-d; _=P [p]. d ;
// if(b>_){/*]b */
// P[p].d=b;}{; }
// #undef/*pqdz'.*/ e// ;
// #define/*s8qdb]*/e/**/0 //
// //<<.<<.----.>.<<.>++.++< .[>]
// /*P[*/P[p].b++;continue;}}}t= stdout;
// for (p=1;p<I;p++){/**/if(P[p].b>i ){i=P[p].b;}}
// if (O){for(p=0;p<i;p++){q=0;/*[*/while(I >++q){_=P[q].p-P[q ].q;
//b= 0;if(_<P[q ].o){while(012-*P[q].p) {putchar(*(P[q].p++));b++;}P[q]. p++;
//} ;while (P[ q].d>b++)putchar(040);} putchar(10);}return 0;}p =1;
// for(; p<I ;p++)fwrite(P[p] .q,P[ p].o,1,t);return 0 ;}//
// #/*] ]<. [-]<[-]<[- ]<[ -]< [- ]<;*/elif e //b
// |(1 << ( __LINE__ /* >> `*//45)) | 01U
// # /* */ endif //
#include<bits/stdc++.h>
typedef long long ll;
#define N 4000005
using namespace std;
ll ans=0;
int n,m,d[N],head[N],tot=0;
struct Edge{
int u,v,next;
}G[N];
void addedge(int u,int v){
G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot;
G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot;
}
struct SuffixAutoMaton{
int ch[N][10],fa[N],l[N];
int rt,last,cnt;
void init(){rt=last=++cnt;}
int newnode(int x){l[++cnt]=x;return cnt;}
int ins(int p,int c){
if(ch[p][c]){
int q=ch[p][c];
if(l[q]==l[p]+1)last=q;
else{
int nq=newnode(l[p]+1);last=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];fa[q]=nq;
for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
}
}
else{
int np=newnode(l[p]+1);last=np;
for(;p&&(!ch[p][c]);p=fa[p])ch[p][c]=np;
if(!p)fa[np]=rt;
else{
int q=ch[p][c];
if(l[q]==l[p]+1)fa[np]=q;
else{
int nq=newnode(l[p]+1);
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
}
}
}
return last;
}
void calc(){
ans=0;
for(int i=1;i<=cnt;i++)ans+=l[i]-l[fa[i]];
}
}sam;
int val[N];
void dfs(int u,int f,int p){
int t=sam.ins(p,val[u]);
for(int i=head[u];i;i=G[i].next){
int v=G[i].v;if(v==f)continue;
dfs(v,u,t);
}
}
inline int read(){
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
int main(){
n=read();m=read();sam.init();
for(int i=1;i<=n;i++)val[i]=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
addedge(u,v);d[u]++;d[v]++;
}
for(int i=1;i<=n;i++)if(d[i]==1)dfs(i,0,sam.rt);
sam.calc();
cout<<ans<<endl;
}
```
啊？你问我哪来的御坂妹妹？知乎上抄来的。
http://www.ioccc.org/2013/misaka/misaka.c