You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 30 Mar '16, 20:15

vibhor3gupta's gravatar image

4★vibhor3gupta
111
accept rate: 0%

edited 01 Apr '16, 16:47

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,677
×2,168
×1,672
×847
×726
×708
×6
×2

question asked: 30 Mar '16, 20:15

question was seen: 872 times

last updated: 01 Apr '16, 16:47