YZOJ P2242 [ZJOI 2015]Substring

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 \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}\) 。

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注