Finding two paths in a tree ?

Revision en1, by svg_af, 2016-03-09 16:03:45

Hello There

I came across this problem on spoj

we're given a tree and we have to find two paths that don't share vertices and which sum of their length is maximum

no i got an idea where we compute the longest path for each subtree rooted with vertex u and there answer is the max sum for each node where for each node we sum the longest path in the subtree rooted with u and the longest path in the entire tree minus the sub tree rooted with u

the latter was a bit confusing for me and i couldn't come up with the solution

any advises or hints about how to compute the longest path in the tree minus the subtree rooted with u for each vertex u would be greatly appreciated

Tags tree, dp, path, diameter

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English svg_af 2016-03-09 16:03:45 759 Initial revision (published)