title: How to find the max distance between a set of nodes on a tree?
body: <p>I have a set of n nodes on a (non-binary) tree. I want to find the maximum of the distances between any two of the nodes. (I define the distance between two nodes to be the sum of the distances between those nodes and their lowest common ancestor).</p>
  
  <p>I can easily solve this problem in O(n^2) by just computing the distance between each node to each other node and getting the maximum, however I'm hoping for something better as this is far too slow* for my application scenario.</p>
  
  <p><em>(Extra info: In my application scenario, these nodes are actually files and the tree is a directory structure. Therefore, the tree is quite shallow (depth &lt; ~10), but it may have 300,000+ nodes. The sets of files can be anywhere between ~3-200</em> in size. Effectively, I'm trying to figure out how far spread out are my files in each set.)*</p>
  
  <p><strong>Edit:</strong> Perhaps I can ask an equivalent question to prompt more answers: Consider a subset of the original tree that only contains the nodes in my set and the nodes necessary to connect them. Then the question becomes: <strong>How do I find the longest simple path in an undirected acyclical graph?</strong> </p>
  
  <p>*<strong>Edit 2:</strong> As didierc pointed out, I actually should be considering sets of folders not files. This makes my sets smaller and the exhaustive approach may be fast enough. Still, it would be beneficial to see a faster solution, and I'm curious to see if there is one.</p>