We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Hi gkeller2, I wrote the following code, treating the tree as a graph and employing dfs. However, I am getting errors from testcase6 onwards, and i don't know if it's a stack memory issue or not, because I checked testcase5, and it is just as big as testcase6, can you help me decipher what's wrong with my code?
importjava.util.*;classtreeCut{privateintvalues[];privateinttree[][];privateintvisited[];privateintn;privateintsum;privateintmin;publictreeCut(intn){this.n=n;values=newint[n+1];tree=newint[n+1][n+1];visited=newint[n+1];sum=0;min=Integer.MAX_VALUE;}publicvoidaddValue(intnode,intvalue){values[node]=value;sum+=value;}publicvoidnewEdge(intu,intv){setEdge(u,v);setEdge(v,u);}privatevoidsetEdge(intu,intv){tree[u][0]+=1;tree[u][tree[u][0]]=v;}privateinttraverse(intnode){visited[node]=1;inttreeSum=values[node];inti,diff=0;// System.out.println("\n"+"At node "+node);for(i=1;i<=tree[node][0];i++){if(visited[tree[node][i]]==0)treeSum+=traverse(tree[node][i]);}// System.out.println("For node - "+node);// System.out.println("Sum from this tree - "+treeSum);// System.out.println("Rest of the tree - "+(sum-treeSum));diff=(int)Math.abs((2*treeSum)-sum);// System.out.println("Difference - "+diff);if(diff<min)min=diff;returntreeSum;}publicintgetMinSum(){// System.out.println("Net Tree Sum - "+sum);traverse(1);returnmin;}publicstaticvoidmain(Stringargs[]){try{Scanners=newScanner(System.in);intn=s.nextInt();inti,u,v;treeCuttemp=newtreeCut(n);for(i=1;i<=n;i++)temp.addValue(i,s.nextInt());for(i=1;i<n;i++){u=s.nextInt();v=s.nextInt();temp.newEdge(u,v);}System.out.println(temp.getMinSum());}catch(Exceptione){System.out.println("Exception caught - "+e);}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Cut the Tree
You are viewing a single comment's thread. Return to all comments →
Hi gkeller2, I wrote the following code, treating the tree as a graph and employing dfs. However, I am getting errors from testcase6 onwards, and i don't know if it's a stack memory issue or not, because I checked testcase5, and it is just as big as testcase6, can you help me decipher what's wrong with my code?