Hi all,

I was trying to solve the problem mentioned in the title of this post using the trie data structure, but something seems to be inefficient/inaccurate in my code.(You may refer to the problem statement here).

Below is presented my solution:-

//God's Grace
#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
#include <list>
#include <string>
#include <cmath>
#include <stack>
#include <cstdio>
#include <fstream>
#include <climits>
#include <set>
#include <vector>
#include <tuple>
#include <cstring>
#include <functional>
#include <utility>

using namespace std;



#define endl '\n'
#define f(k,a,b) for(int k=(a);k<(b);k++)
#define vi vector <int>
#define vvi vector <vector <int> >
#define   vii vector <pair <int, int > >
#define lli long long int
#define pii pair <int,int>
#define piii pair< pair<ll int,ll int>, ll int >
#define fsd fflush(stdout);
void tc(int i){cout<<"Case #"<<i+1<<": ";}
void yes(){cout<<"YES"<<endl;}
void no(){cout<<"NO"<<endl;}
void impb(){cout<<"IMPOSSIBLE"<<endl;}

const int fix  = 1e9 +7;
const short int ALPHABET_SIZE=26;
int cnt=0;
typedef struct trie_node{
	struct trie_node *links[ALPHABET_SIZE];
	bool ew;
	int no_of_words;
}tride;

tride* getnew(void){
	tride* fresh = new tride;
	fresh->ew=false;
	fresh->no_of_words=0;
	f(i,0,ALPHABET_SIZE){
		fresh->links[i]=NULL;
	}
	return fresh;
}


void tride_insert(tride* root, string key){
	tride* temp = root;
	f(i,0,key.length()){
		int index  = key[i] &mdash; 'A';
		if(!temp->links[index]){
			temp->links[index] = getnew();
			//cnt++;
		}
		temp = temp->links[index];
	}
	temp->ew=true;
}

int tride_size(tride* root){
	if(root==NULL)
		return 0;

	int ans=0;
	if(root->ew){
		ans=1;
	}
	f(i,0,ALPHABET_SIZE){
		ans+=tride_size(root->links[i]);
	}
	//cout<<ans<<endl;
	return root->no_of_words=ans;
}

int tride_search(tride* root, string key){
	tride* temp = root;
	f(i,0,key.length()){
		int index = key[i] &mdash; 'A';
		if(!temp->links[index])
			return 0;
		temp  = temp->links[index];
	}

	if(temp!=NULL/*&&temp->ew*/){
		return tride_size(temp);
	}
	return 0;
}
int aux=0;
void answer(tride *root){

	if(root==NULL)
		return;

	int temp = 0;
	f(i,0,ALPHABET_SIZE){
		if(root->links[i]&&root->links[i]->no_of_words>1){
			answer(root->links[i]);
		}else if(root->links[i]&&root->links[i]->no_of_words==1){
			temp++;
		}
		//if(root->links[i])
		//cout<<root->links[i]->no_of_words<<" ";
	}
	if(root->ew){
		temp++;
	}
	//cout<<endl;
	if(temp==1){
		aux++;
	}

	//cout<<temp<<endl;
	if(temp>=2){
		cnt++;
	}
}

int main() {

int t;
cin>>t;
f(i,0,t){
int n;
cin >>n;

string resp;
tride* head =getnew();
f(j,0,n){

		cin>>resp;
		reverse(resp.begin(),resp.end());
		//cout<<resp<<endl;
		tride_insert(head,resp);

}

	tride_size(head);
f(q,0,ALPHABET_SIZE){
	aux=0;
	answer(head->links[q]);
	cnt+=(aux/2);
}
	tc(i);
cout<<2*cnt<<endl;
cnt=0;

}
	return 0;
}

This worked correctly for the small dataset but gave me a 'WA' for the large dataset. Can someone please explain me why ? It will be very helpful if someone could give me a counter test case. Thanks in advance!