There are N nodes connected by N-1 edges. The weight of each edge is 1 and it's possible to reach any node from any other node.

We are given a subset of nodes. We need to pair(1 to 1 mapping) the subset of nodes and find the maximum distance possible after pairing.

For example:
N = 8 ( Number of nodes) 
subset of nodes = [2,4,5,6]

Graph: 

   7
   |
6--1--2--8 
   | 
   3--4
   | 
   5

Solution
Maximum distance: 
    Pairs
    (2,4) : 2-1-3-4 => distance 3 
    (6,5) : 6-1-3-5 => distance 3 
    max distance = 3 3 = 6
    It's possible to form other pairs but max distance will always comes out to 6.

How to calculate max distance?

CodePudding user response：

First of all, as there are n nodes, and n-1 edges always connecting them, this must be a tree.

Let's say, length of subset, k.

The obvious approach is to run bfs for all the k nodes, it will give you all the distances from the nodes from the subset.

Then, we can do a nested loop (k^2) to find which pair has the largest distance.

Or, we can keep a max_distance variable, and update the max_distance while running the bfs, it will get rid of the extra k^2 term.

We can further optimize this using an LCA. Once we select a root and have the LCAs, we can find any distance pair easily by, d(node1, node2) = d(node1) d(node2) - 2 x lca(node1, node2)

CodePudding user response：

For the first find the centroid of the tree. Next perform the following operations for each pair of vertices: Find the distance between vertices and the centroid of the tree. The sum of these values is the maximum distance between the vertices.