It is not NP-hard for trees. For example, you can do the following.
The roots of the tree are arbitrary.
For each vertex v, calculate the optimal solution bounded by the v subtree.
In addition, for each v for each path p that includes the v parent edge, it computes the optimal solution bounded by the v subtree, except for the path p.
(2) and (3) can be calculated using solutions of smaller problems inside the v subtree.
It is probably easier to look at steps 1, 2 and 3 and find out what the repetition is, but just to give you an idea, (2) can be calculated by taking a maximum of several solutions: one that summarizes the solutions for children v (t ie the sum of the decisions created in step 2 for each child), and one for each path, which includes v plus the solutions for step 2 for other children (this will essentially include the sum of one or two decisions obtained in step 3 for v children, plus the sum of the decisions obtained in stage 2 for other children).
source share