PROBLEM LINK :
Author : Rahul Agarwal
Tester : Rahul Agarwal
Editorialist : Rahul Agarwal
Difficulty :
Easy - Medium
PREREQUISITES :
Trees , DFS
PROBLEM :
Find the number of sub-trees of a given a tree
As the answer could be quite large, print your answer modulo 10^9 + 7.
Code is given. Debug it.
Flawed code :
include
using namespace std;
vector g[1000000+10];
long long tem,mod = 1e9 + 7,dp[100000+10];
long long dpsum(int n)
{
tem=0;
for(int i=0;i!=n;i++)
{
tem = (tem + dp[i])%mod;
}
return tem;
}
void dfs(int n,int p=-1)
{
dp[n]=1;
for(int i=0;i!=g[n].size();i++)
{
if(g[n][i] != p)
{
dfs(g[n][i],n);
dp[n] = (dp[n] * dp[g[n][i]]);
if(dp[n] > mod) dp[n] -= mod;
}}}
int main(){
int t;
scanf("%d",&t);
int v,x,y;
while(t–){
scanf("%d",&v);
for(int i=0;i != v-1;i++){
scanf("%d %d", &x , &y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(v);
printf("%lld\n", dpsum(v));
}
return 0;
}
EXPLANATION :
In this question,
let dp[u] = answer for the vertex u.
Let us assume that we have calculated the answer for the sub-trees formed by the children of the vertex v, then for answer for vertex v will be product of (1+dp[u]), where u is the child of vertex v.
That was the main error in the code, the rest of the code can be view at, corrected code