YZOJ P2242 [ZJOI 2015]Substring
时间限制：1000MS 内存限制：524288KB
难度：\(8.0\)
-
题目描述
给出一棵 \(n\) 个节点、叶子不超过 \(20\) 个的树，每个节点上有 \(0\) 到 \(c-1\) 的数字。
树上任意两点 \(A\)、\(B\) 间的有向路径 \(A \rightarrow B\) 形成了一个字符串（\(A \rightarrow B\) 和 \(B \rightarrow A\) 构成的串相反）。
求总共有多少个互不相同的字符串。
-
输入格式
第一行两个数，\(n, c\) 。
第二行 \(n\) 个 \(0\)~\(c-1\) 间的数，表示每个节点的颜色。
接下来 \(n-1\) 行，每一行表示一条树边。
保证叶子个数不超过 \(20\)。
-
输出格式
一个整数，表示不同的字符串数。
-
样例输入
|
1 2 3 4 5 6 7 8 |
7 3 0 2 1 2 1 0 0 1 2 3 4 3 5 4 6 5 7 2 5 |
-
样例输出
|
1 |
30 |
-
数据规模与约定
\(1 \leq n \leq 10000, 1 \leq c \leq 10\) 。
Source: BZOJ 3926
注意到所有叶子结点个数不超过 \(20\) ，所以可以以每个叶子结点为根，向上 DFS 出一棵 Trie树，然后再合并成一棵包含所有如题所述子串的大 Trie树，统计它的不同子串的个数。
DFS 建立 广义SAM 的时候注意：每次扩展SAM时 last 赋值为其父亲的 last 即可。
统计不同子串个数就是 \(\sum\limits_{x}{max_x-min_x+1}\) 。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } int gcnt,ghead[105050],gnext[205050],gnode[205050]; int d[105050]; inline void insertLine(register int s,register int t) { gnext[++gcnt]=ghead[s],ghead[s]=gcnt,gnode[gcnt]=t; gnext[++gcnt]=ghead[t],ghead[t]=gcnt,gnode[gcnt]=s; d[s]++,d[t]++; } #define CHARSET 10 int cnt,mxval[5050505],parent[5050505],ch[5050505][CHARSET],root,last; inline int CreateNode(register int val=0) { parent[++cnt]=0,mxval[cnt]=val; for(register int j=0;j<CHARSET;j++) ch[cnt][j]=0; return cnt; } inline int ExtendNode(register short c) { register int nw=CreateNode(mxval[last]+1),now=last; for(; now && !ch[now][c]; now=parent[now]) ch[now][c]=nw; if(!now) return parent[nw]=root,last=nw; register int q=ch[now][c]; if(mxval[q] == mxval[now]+1) return parent[nw]=q,last=nw; register int b=CreateNode(mxval[now]+1); for(register int j=0;j<CHARSET;j++) ch[b][j]=ch[q][j]; parent[b]=parent[q],parent[q]=parent[nw]=b; for(; now && ch[now][c]==q; now=parent[now]) ch[now][c]=b; return last=nw; } short color[105050]; inline void DFS(register int o,register int fa,register int tlast) { last=tlast,ExtendNode(color[o]),tlast=last; for(register int j=ghead[o];j;j=gnext[j]) if(gnode[j] != fa) DFS(gnode[j],o,tlast); } int main() { register int N=getnum(),C=getnum(); for(register int i=1;i<=N;i++) color[i]=getnum(); for(register int i=1;i<=N-1;i++) insertLine(getnum(),getnum()); root=last=CreateNode(); for(register int i=1;i<=N;i++) if(d[i]==1) DFS(i,0,1); long long ans=0; for(register int i=2;i<=cnt;i++) ans+=mxval[i]-mxval[parent[i]]; printf("%lld\n",ans); return 0; } |