1
$\begingroup$

I've got one very hard problem.

Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes. Algorithm should run in poly time.

Can you help me to solve it ?

  • 0
    Ok, thank you very much.2012-06-17

1 Answers 1

1

Hint:

Root the tree in an arbitrary vertex and going bottom-up consider the best solution for every subtree if the top node of it is taken (and therefore none of the children are) or when it is not taken (so for any child you can, but don't have to take it).