[ppblbyzu] Longest path between nodes in a subset

Given a maze whose graph structure is a tree, find the two nodes on the edge of the maze with the largest distance between them.  That is, where on the border should we put the maze entrance and exit to make the maze as difficult as possible?

If we do not restrict the endpoints of the maximal path to edge nodes, then finding the graph diameter of a tree can be solved in reasonable time and space by the classic algorithm involving running breadth-first search twice.  Consider modifying the algorithm to return (then use) the last edge node visited by each breadth-first search.  Does this solve our problem?  If not, is it a good approximation algorithm?  How much can it deviate from optimal?

An algorithm for computing all-pairs shortest paths on a general graph, e.g., Floyd-Warshall, does solve our problem, but it requires way more space.