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