I came across this problem today.
I can only think of an O(n^2 + n*Q) solution.
My solution: 1. Store all nodes in a path from node u to node v for all possible u and v. 2. For each set query, use a bool array and mark all the nodes involved in connecting all nodes in the set. 3. Minimum number of edges required is number of marked nodes
This however takes O(n^2 + n*Q).
I'm pretty sure there are better solutions than this one. Please help me out. Question Link: https://www.hackerrank.com/contests/algorithms-2/challenges/another-tree-problem
Run a dfs once to store all vertices in some order (maybe pre-order, I'm not sure). This kind of sorts vertices from left to right. For every vertex remember its position in this order.
Then for a query with K vertices, sort them according to the order you found earlier. If you know have vertices A, B, C, D, change this list into A, lca(A, B), B, lca(B, C), C, lca(C, D), D. Now, I think, this gives us a sequence of edge-disjoint paths.