GCJ2019-1A3: Alien Rhyme

#include <bits/stdc++.h>
using namespace std;

struct node {
    bool isWord;
    node **nxt;
    node(){
        isWord = false;
        nxt = new node*[26];
        for(int i = 0; i < 26; ++i){
            nxt[i] = NULL;
        }
    }
};

void addWord(string &str, int i, node *root){
    if(i == (int)str.size()){
        root -> isWord = true;
        return;
    }
    int nxtIdx = str[i] - 'A';
    if(root -> nxt[nxtIdx] == NULL){
        root -> nxt[nxtIdx] = new node();
        addWord(str, i + 1, root -> nxt[nxtIdx]);
    } else {
        addWord(str, i + 1, root -> nxt[nxtIdx]);
    }
}

void deleteTrie(node *root){
    for(int i = 0; i < 26; ++i){
        if(root -> nxt[i] != NULL){
            deleteTrie(root -> nxt[i]);
        }
    }
    delete(root);
}

int cnt;
int DFS(node *root){
    int wordCnt = (int)root -> isWord;
    for(int i = 0; i < 26; ++i){
        if(root -> nxt[i] != NULL){
            wordCnt += DFS(root -> nxt[i]);
        }
    }
    if(wordCnt >= 2){
        wordCnt -= 2;
        cnt += 2;
    }
    return wordCnt;
}

int main(){

    int Q;
    scanf("%d", &Q);
    for(int q = 1; q <= Q; ++q){
        cout << "Case #" << q << ": ";
        int nStr;
        node *root = new node();
        scanf("%d", &nStr);
        for(int i = 1; i <= nStr; ++i){
            string str;
            cin >> str;
            reverse(str.begin(), str.end());
            addWord(str, 0, root);
        }
        cnt = 0;
        for(int i = 0; i < 26; ++i){
            if(root -> nxt[i] != NULL){
                DFS(root -> nxt[i]);
            }
        }
        cout << cnt << '\n';
        deleteTrie(root);
    }

    return 0;
}