「REOI-1」渺茫的希望

Luogu
IDLGP8464
Time1000ms
Memory128MB
DifficultyP6
洛谷原创洛谷月赛
其中有一件令威廉记忆颇深的事情,便是活泼的少女们会时常的“抓住”威廉,让他来与她们一起读书。每逢此时,威廉总要开玩笑说“我脑筋超棒的哦,只要是五百年以上的古书尽管找我念”云云。但一来二去终究还是拗不过少女们的请求,半推半就的讲述一些以前的故事。长此以往,威廉在讲故事之余,会间或的用那些五百年以前的文字来和少女们玩一些“文字游戏”,游戏的规则如下: 威廉会给出一串由小写英文字母组成的字符串 $S$ ,其中每一个古文字便是由它的子串构成——如果我们说两个古文字不同,那么当且仅当这两个子串长度不同或长度相同且有任意一位不同——当两个不同的古文字拼凑在一起组成一个词语时,其音律、词义等各方面也会有所不同,于是威廉为了方便,就定义了一个“意境值”来衡量拼凑成的词语的质量。意境值的计算公式便是这两个本质不同子串在 $S$ 中出现的次数之和加上这两个本质不同子串的最长公共前缀的长度。 而当少女们把所有这些古文字拼凑成了一个句子后,威廉惊讶的发现,这个句子可以视作为任意两个古文字连边形成的完全图的最小生成树。他于是一鼓作气,推理出了这个句子的意境值的公式——这些最小生成树(因为最小生成树可能不唯一)的边权和。 其中,两个古文字的边权与她们组成的词语的意境值在数值上相等。 现在,威廉又在和少女们玩文字游戏了,威廉现在给出了一个字符串 $S$ ,但由于这是他临时起意写出的,他也不知道如果将它拼凑成一个句子,意境值究竟是多少——于是乎,威廉将求助的目光投向了你。 ---- 简要题意: 给定一个由小写英文字母组成的字符串 $S$ ,设在两个本质不同子串之间连边的权值为两个子串在 $S$ 中出现的次数之和加上这两个子串的最长公共前缀的长度,求对所有本质不同子串做最小生成树的边权之和(不含空串)。 ## Input 第一行一个整数 $n$ 。 接下来一行 $n$ 个字符表示威廉给出的字符串 $S$ 。 ## Output 一行一个整数,表示这个句子的意境值。 [samples] ## Background 威廉在与妖精们相处的日子里,留下了不少幸福的记忆。 ## Note #### 样例解释 #1 ![](https://cdn.luogu.com.cn/upload/image_hosting/fqjg81g9.png) 如图所示为一种最小生成树,边权和为 $15$。 #### 数据范围 对于 $10\%$ 的数据,$|S|\le 100$。 对于 $30\%$ 的数据,$|S|\le 1000$。 对于 $100\%$ 的数据,$1\le|S|\le 10^5$。
Samples
Input #1
4
abab
Output #1
15
API Response (JSON)
{
  "problem": {
    "name": "「REOI-1」渺茫的希望",
    "description": {
      "content": "其中有一件令威廉记忆颇深的事情,便是活泼的少女们会时常的“抓住”威廉,让他来与她们一起读书。每逢此时,威廉总要开玩笑说“我脑筋超棒的哦,只要是五百年以上的古书尽管找我念”云云。但一来二去终究还是拗不过少女们的请求,半推半就的讲述一些以前的故事。长此以往,威廉在讲故事之余,会间或的用那些五百年以前的文字来和少女们玩一些“文字游戏”,游戏的规则如下: 威廉会给出一串由小写英文字母组成的字符串 $S$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8464"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "其中有一件令威廉记忆颇深的事情,便是活泼的少女们会时常的“抓住”威廉,让他来与她们一起读书。每逢此时,威廉总要开玩笑说“我脑筋超棒的哦,只要是五百年以上的古书尽管找我念”云云。但一来二去终究还是拗不过少女们的请求,半推半就的讲述一些以前的故事。长此以往,威廉在讲故事之余,会间或的用那些五百年以前的文字来和少女们玩一些“文字游戏”,游戏的规则如下:\n\n威廉会给出一串由小写英文字母组成的字符串 $S$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments