The 4th(2009) ACM Programming Contest of HUST - Onsite Contest

From: 2009-12-06 12:00:00 To: 2009-12-06 17:00:00 Now: 2017-09-20 01:09:55 Status: Public

J - Trie

Time Limit: 1s Memory Limit: 128MB

Submissions: 112 Solved: 39
Description
In computer science, a trie, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Each position in the tree shows what key it is associated with and All the descendants of a node have a common prefix of the string associated with that node, have and only have one more character than its father node. the root of the trie is associated with the empty string. For example, if we put 6 words of “to”, “tea”, “ted”, “ten”, “a”, “inn” to a trie, it will be the form of figure. In the computer science, a trie is a tree. For a tree, we define the leave node is the node without any descendants and only have an edge connect in. So in this example, the leave node is “to”, “tea”, “ted”, “ten”, “a” and “inn”. And we define the distance between two node is the minimum edge from a node to another node must pass. So the distance between “a” and “te” is 3, “to” and “inn” is 5. Finally, we define the value of a node is the sum of the node to the entire leave node’s distance. And the value of a tree is equal the value of a node which have the minimum value. Now give you a list of words. Put them into a trie, and calculate the value of this trie.
Input
The first line is T, indicate there are T cases. For each case, the first line is N, indicate there are N words. Next N lines, each line have a word only include the lower case letters and no two words are the same. (N<=50 and the length of a word less than 10)
Output
For each case output a line with the value of the trie.
Sample Input
2
6
a
to
tea
ted
ten
inn
4
sa
sb
sc
sd
Sample Output
Case #1: 13
Case #2: 5



/////////////////////////////////////
For the second case, if the root has only one child, it’s a special leaf and must be calculate.
Hint
Source
Hong Zehua, HUST Campus 2009