You are given a complete, balanced N-Ary Tree and must support Q queries. There are 3 kinds of queries. Return true or false depending on whether the query was successful.
Lock(v, id) — Lock vertex v for user — id Unlock(v, id) — If vertex v is locked by the same id, unlock it. Upgrade(v, id) — If v is unlocked and has at least one locked vertex in it’s subtree and every locked vertex in the subtree of v is locked by id, unlock them and lock v instead. Further, here are some additional constraints
A vertex cannot be locked if it has any locked ancestors or descendants, by any ID. When a vertex is upgraded, it’s locked descendants are automatically unlocked. An upgrade operation is not possible if the vertex is already locked or has any locked ancestors An unlock operation is only possible if the vertex is already locked and locked by the same id
PS — the lock and unlock function is already done in Log n, Please try to give an approach on how to store information inNode so that the upgrade function takes Log n time.