breathe_fire's blog

By breathe_fire, 5 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

Full text and comments »

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