Weird time complexity for void and returning DFS in tree dp question

help
,
1

I tried to solve tree count question Tree Count April Circuit hackerearth appeared in hackerearth april circuits but could solve in only partially when using int returning DFS and DP which i found very slow, after the contest i tried to solve it with void DFS and DP which strangely came out very fast and i got full AC.
I couldn’t find how these two dfs which appeared to have similar time complexity have different time complexity.
Upon using a count variable it came out that returning DFS function created 999001 recursive function calls whereas Void DFS function only took 1000000 calls ,
even then they took different time to give solution
, can someone help with the time complexities of the two @ssjgz @cubefreak777 @lotthbrok @akshitm16

The first function gave AC and second TLE
Submission with TLE
Submission with AC

Two Functions 

//==================RETURN vs VOID in Tree DP=============================================//
//==================vi adj[N] contain a tree=================================//

dp=vector<vector<int>>(n+1,vector<int>(1000+1,-1));
 
//==========================================FIRST FUNCTION==============================================//
 
//initial call dfs(1,-1);

int cct=0; 

inline void dfs(int node, int pa){
    cct++;
 
    if(adj[node].size()==1){  
	int ansi=0; for(int i=1;i<=1000;i++){ ansi++; dp[node][i]=ansi; }  
	return; } //i.e leaf node
 
    for(auto u:adj[node]){ if(u!=pa){ dfs(u,node);} }
    
    int ans=0;
    for(int i=1;i<=1000;i++){ 
        ll ansi=1;
        for(auto u:adj[node]){ 
            if(u!=pa){
                ansi*=(ll)dp[u][i]; if(ansi>=mod1){ ansi%=mod1; }
            }
        }
        ans+=ansi; if(ans>=mod1){ ans%=mod1; }
        dp[node][i]=ans;
    }
 
 
}// cct value found after execution=1000000
 
//==========================================SECOND FUNCTION==============================================//
 
//initial call dfs(1,-1,1000);
 
int cct=0;

inline int dfs(int node, int pa, int x=1000){
 
    if(dp[node][x]!=-1){return dp[node][x]; }

 cct++;
    int ans=0;
 
    for(int i=1;i<=x;i++){ 
        ll ansi=1;
        for(auto u:adj[node]){ 
            if(u!=pa){
                ansi*=(ll)dfs(u,node,i); if(ansi>=mod1){ ansi%=mod1; }
            }
        }
        ans+=ansi; if(ans>=mod1){ ans%=mod1; }
        dp[node][i]=ans;
    }
 
return ans;
 
}// cct value found after execution=999001
2

I am not sure about this but are you checking the following part in the first code?

if(dp[node][x]!=-1){return dp[node][x]; }

And it seems weird to me, how’s second code giving TLE while the first one gives AC? :thinking:

3

Ya, that’s because i’m checking if dp[node][x] is already calculated, if yes then return else, it is calculated.
This line is not weird in itself and is most pobably not the reason for TLE.

4

Oh i understood your question, actually that’s because I’m already sure that the child states are already calculated and I don’t need to check if it is calculated or not