Shortest Names

In a strange village, people have very long names. For example: aaaaa, bbb and abababab.

You see, it's very inconvenient to call a person, so people invented a good way: just call a prefix of thenames. For example, if you want to call `aaaaa', you can call `aaa', because no other names start with`aaa'. However, you can't call `a', because two people's names start with `a'. The people in the villageare smart enough to always call the shortest possible prefix. It is guaranteed that no name is a prefix ofanother name (as a result, no two names can be equal).

If someone in the village wants to call every person (including himself/herself) in the village exactlyonce, how many characters will he/she use?

 

Input 

The first line contains T (T10), the number of test cases. Each test case begins with a line of oneinteger n (1n1000), the number of people in the village. Each of the following n lines contains astring consisting of lowercase letters, representing the name of a person. The sum of lengths of all thenames in a test case does not exceed 1,000,000.

 

Output 

For each test case, print the total number of characters needed.

 

Sample Input 

 

13aaaaabbbabababab

 

Sample Output 

 

5

 

---

Problemsetter: Rujia Liu, Special Thanks: Yiming Li, Feng Chen, Jane Alam Jan

#include <stdio.h>
#include <string.h>
struct Trie {
    bool n;
    int link[26], cnt;
} Node[1048576];
int TrieSize;
int insertTrie(const char *str) {
    static int i, idx;
    idx = 0;
    for(i = 0; str[i]; i++) {
        if(!Node[idx].link[str[i]-'a']) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[str[i]-'a'] = TrieSize;
        }
        idx = Node[idx].link[str[i]-'a'];
        Node[idx].cnt++;
    }
    Node[idx].n = true;
    return 0;
}
long long ans;
void dfs(int nd, int dep) {
    int i;
    for(i = 0; i < 26; i++) {
        if(Node[nd].link[i]) {
            dfs(Node[nd].link[i], dep+1);
            if(Node[nd].cnt != 1 && Node[Node[nd].link[i]].cnt == 1)
                ans += dep;
        }
    }
}
char str[10000];
int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        while(n--) {
            scanf("%s", str);
            insertTrie(str);
        }
        ans = 0;
        dfs(0, 1);
        printf("%lld\n", ans);
    }
    return 0;
}