CODEWITHSUNDEEP
algorithmgraphtreeshortest-pathbreadth-first-search
Number945
Number945

Reputation: 4940

Nearest node in a tree

Recent I encountered this problem on trees whose solution I found in O(n*q) . I am thinking if there is much better way to deal this with lesser complexity.

The problem is here as follows :

Given an unweighted tree of 'n' nodes ( n>=1 and n can go to 105 ) , Its nodes can be special or non special. Node 1 is always special and rest non special initially. Now ,There are two operations :

1.we can update any non special node to special node by an update operation by "U Node_Number"

OR

2.At any time , we can ask user "Q Node_Number" which should return that special node in tree closest to "Node_Number".

These operations can also go upto 105.

My Solution :

I thought of creating adjacency list. For operation 1, I can keep record of special or Non special by boolean flag. But for operation 2 , my solution comprises of doing BFS whenever "Q Node_Number" is asked taking "Node_Number" as root to begin my BFS.

But complexity is quadratic. Is this the most optimal way of going about this problem ?

Upvotes: 1

Views: 521

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Here's an O(n^1.5 + n^0.5 q)-time algorithm via a sqrt decomposition. We need a constant-time distance oracle (this is basically least common ancestors). The idea is, every n^0.5 times a node is made special, perform a breadth-first search from all special nodes, which yields for each node in the tree the closest node that is currently special. On each query, take the closest of (i) the nodes that were special as of the last breadth-first search (ii) the at most n^0.5 newly special nodes.

As I mentioned in the comments, I expect that there's a very complicated O((n + q) log n)-time algorithm via top trees.

Upvotes: 1

Related Questions