I think that you can solve it using dynamic programming. For instance,
let d[u] = the weight of the subtree rooted at u. Then d[u] =
weight[u] + sum_{v is a child of u} d[v]. Now it's your turn to think
about how to prove you can compute d[u] for all u as efficiently as
possible (e.g., can you find a linear time solution?).On Jan 29, 2:07 am, Debajit Adhikary <[EMAIL PROTECTED]> wrote: > Lets say I have a weighted tree (with positive, zero and negative > weights for each node). > How could I best find the subtree having the maximum weight? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
