Connecting nodes in a tree

A hypotetical question. Say I'm given a tree T and a list of pair of nodes (x, y) in T. I'm asked how many of the pairs I can connect simotaneously (connect x with y) using each edge开发者_运维百科 in T at most once.

How would one to that?

It isn't NP-hard for trees. You can do the following, for example.

1. Root the tree arbitrarily.

2. For each vertex v, compute the optimal solution that is confined to v's subtree.

3. Additionally, for each v, for each path p that includes v's parent edge, compute the optimal solution that is confined to v's subtree except for path p.

(2) and (3) can be computed using the solutions to the smaller problems within v's subtree.

It's probably easier to look at steps 1, 2, and 3, and figure out the recurrence yourself, but just to give you an idea, (2) can be computed by taking the maximum of several solutions: one that sums the solutions for the children of v (i.e., the sum of the solutions produced in step 2 for each child), and one for each path that includes v plus the step 2 solutions for the other children (this will essentially include the sum of one or two solutions produced in step 3 for v's children, plus the sum of the solutions produced in step 2 for the other children).