P8464 "REOI-1" A Faint Hope

During the days William spent with the fairies, he left behind many happy memories.

One thing that William remembered especially well was that the lively girls would often “catch” William and have him read books with them. Whenever this happened, William would always joke, “My brain is super good. If it’s an ancient book older than five hundred years, just come find me to read it,” and so on. But after being asked again and again, he still could not refuse their requests, and would half-push-half-agree to tell some stories from the past. Over time, besides telling stories, William would sometimes use those writings from more than five hundred years ago to play some “word games” with the girls. The rules are as follows: William gives a string $S$ consisting of lowercase English letters. Each ancient character is represented by a substring of $S$. If we say two ancient characters are different, then and only then their corresponding substrings have different lengths, or have the same length but differ at some position. When two different ancient characters are put together to form a word, its rhythm, meaning, and other aspects will also differ. For convenience, William defines an “artistic conception value” to measure the quality of the formed word. The formula is: the sum of the number of occurrences in $S$ of these two essentially different substrings, plus the length of the longest common prefix of these two essentially different substrings. After the girls pieced all these ancient characters into a sentence, William was surprised to find that this sentence can be regarded as a minimum spanning tree of the complete graph formed by connecting every pair of ancient characters with an edge. He then went further and derived the formula for the artistic conception value of this sentence: the sum of edge weights over all such minimum spanning trees (because the minimum spanning tree may not be unique). Here, the edge weight between two ancient characters is numerically equal to the artistic conception value of the word formed by them. Now William is playing the word game with the girls again. He gives a string $S$, but since he wrote it on a whim, he does not know what the artistic conception value would be if it were pieced into a sentence. So William turns to you for help. ---- Simplified statement: Given a string $S$ consisting of lowercase English letters, define the edge weight between two essentially different substrings as the sum of their numbers of occurrences in $S$ plus the length of their longest common prefix. Find the total edge weight of a minimum spanning tree over all essentially different substrings (excluding the empty string).

The first line contains an integer $n$. The next line contains $n$ characters representing the string $S$ given by William.

Output one integer in one line, representing the artistic conception value of this sentence.

#### Sample Explanation #1  As shown in the figure, this is one possible minimum spanning tree, and the sum of edge weights is $15$. #### Constraints For $10\%$ of the testdata, $|S|\le 100$. For $30\%$ of the testdata, $|S|\le 1000$. For $100\%$ of the testdata, $1\le|S|\le 10^5$. Translated by ChatGPT 5