Trie
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 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