×

CHKTRE - Editorial

 0 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 11●1 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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