Today I was learning Trie from topcoder tutorial Topcoder Trie Tutorial.

I am having confusion in countPrefixes function in topcoder tutorial , i am not able to understand last line of this function.
return countWords(edges[k], prefix)
If someone can explain use of above line.
So i modified countPrefixes function and have written this code for trie following topcoder tutorial . Not sure it is correct way of implementing or not.

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

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int  MOD=1000000007;
const int  INF= int(1e9),ALPHA=26;
string s;
int n;
struct Trie {
    int words,prefixes;
    Trie *edges[ALPHA];
    Trie() {
        words=0;
        prefixes=0;
        for(int i=0;i<ALPHA;i++) {
            edges[i]=NULL;
        }
    }
};
Trie root;

void addword(Trie *vertex,int cur) {
    if(cur==n) {
        vertex->words=vertex->words+1;
    } else {
        vertex->prefixes=vertex->prefixes+1;
        if(vertex->edges[s[cur]-'a']==NULL) {
            vertex->edges[s[cur]-'a']=new Trie;
        }
        
        addword(vertex->edges[s[cur]-'a'],cur+1);
    }
}
int countWords(Trie *vertex , int cur) {
    if(cur==n) {
        return vertex->words;
    } else if(vertex->edges[s[cur]-'a']==NULL) {
        return 0;
    } else {
        return countWords(vertex->edges[s[cur]-'a'],cur+1);
    }
}
int countPrefixes(Trie *vertex , int cur) {
    if(cur==n) {
        return vertex->prefixes+vertex->words ;
    } else if(vertex->edges[s[cur]-'a']==NULL) {
        return 0;
    } else {
        return countPrefixes(vertex->edges[s[cur]-'a'],cur+1);
    }
}
int main()
{
	ios_base::sync_with_stdio(false);

    int q;
    cin>>q;

    while(q--) {
        cin>>s;
        n=s.size();
        addword(&root,0);
    }
    cin>>q;
    while(q--) {
        cin>>s;
        n=s.size();
        cout<<countWords(&root,0)<<" "<<countPrefixes(&root,0)<<endl;
    }
    

	return 0;

}

Ankit has a set of numbers and has recently studied set theory. He has created a power set of this set and is writing a program to compute sum of all elements of all the subsets in power set. Power set of a set S is defined as set of all possible subsets of S.

Set S consist of all the number from 1 to N.

You need to calculate this sum for a given n.

Example:

Given N=3, S={1,2,3} P(S) = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} answer = (1)+(2)+(3)+(1+2)+(1+3)+(2+3)+(1+2+3) = 24

Input First line has T, the total number of test cases. The next T lines contains a number N in each line.

Output T lines giving answer as defined in the question for each N.

Constraints 1<=T<=42 1<=N<=42

Sample Input 1 3

Sample Output 24

I have used bitmask to generate all the subsets to calculate the sum but it is giving tle.

But i have seen people using below code but unable to understand the logic.

#include<stdio.h>
int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
  {
     int n,i;
     scanf("%d",&n);
     long long int ans=1;
     for(i=0;i<n-1;i++)
        ans=ans<<1;
     ans=ans*(n*(n+1))/2;
     printf("%lld\n",ans);
   }
   return 0;
}