breathe_fire's blog

Better way to solve this Tree and Dp problem?
By breathe_fire, 6 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply