Either the root will be included or it will not be. If it's not, then it's equivalent to solving the problem on the subtrees. So let's consider the case when root node is included
Now we keep track of A[node1,node2,reqdWeight] reqdWeight is the sum of wt reqd from paths starting from node1 and node2 Again, let's only see the case when we don't get a path of reqdWeight from one of the nodes alone. Then both node1 and node2 will be included. And i guess it's now a simple DP. @jalaj : i did not read your code but the topview shows that if it works, it is exponential. The algorithm I am suggesting will be polynomial. -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
