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

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
``````

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?

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.

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