CHKTRE - Editorial

PROBLEM LINK :

contest

practice

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