Блог пользователя Breaking_Benjamin

Автор Breaking_Benjamin, история, 9 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Centroid decomposition of a tree.

You can find discussion about this problem (342E - Xenia and Tree) in the link given above.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I think it can be done in Q*(H*log(N)) where H is height of the tree. Do you have a link to this problem?