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 10⁵ ) , 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 10⁵.

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 ?