#1993

Operations on Tree

specialist · 955 · lc medium +32 · 45.1% accepted · 518 likes · top 28%

Description

A tree with n nodes (labeled 0 to n - 1) is described by a parent array where parent[i] is node i's parent and parent[0] = -1 (node 0 is the root). Design a data structure supporting three operations on nodes:

- **Lock**: Lock node num for user only when it is currently unlocked.
- **Unlock**: Unlock node num only when it is locked by user.
- **Upgrade**: Lock node num for user, releasing all its locked descendants, but only when the node is unlocked, has at least one locked descendant, and none of its ancestors are locked.

Implement the LockingTree class with:

- LockingTree(int[] parent) — builds the structure from the parent array.
- lock(int num, int user) — attempts to lock; returns true on success.
- unlock(int num, int user) — attempts to unlock; returns true on success.
- upgrade(int num, int user) — attempts to upgrade; returns true on success.

Example 1:

Input

["LockingTree", "lock", "unlock", "unlock", "lock", "upgrade", "lock"]

[[[-1, 0, 0, 1, 1, 2, 2]], [2, 2], [2, 3], [2, 2], [4, 5], [0, 1], [0, 1]]

Output

[null, true, false, true, true, true, false]

Example 2:

Explanation

LockingTree lockingTree = new LockingTree([-1, 0, 0, 1, 1, 2, 2]);

lockingTree.lock(2, 2); // return true because node 2 is unlocked.

// Node 2 will now be locked by user 2.

lockingTree.unlock(2, 3); // return false because user 3 cannot unlock a node locked by user 2.

lockingTree.unlock(2, 2); // return true because node 2 was previously locked by user 2.

// Node 2 will now be unlocked.

lockingTree.lock(4, 5); // return true because node 4 is unlocked.

// Node 4 will now be locked by user 5.

lockingTree.upgrade(0, 1); // return true because node 0 is unlocked and has at least one locked descendant (node 4).

// Node 0 will now be locked by user 1 and node 4 will now be unlocked.

lockingTree.lock(0, 1); // return false because node 0 is already locked.

Code

class LockingTree:

    def __init__(self, parent: List[int]):
        

    def lock(self, num: int, user: int) -> bool:
        

    def unlock(self, num: int, user: int) -> bool:
        

    def upgrade(self, num: int, user: int) -> bool:
        


# Your LockingTree object will be instantiated and called as such:
# obj = LockingTree(parent)
# param_1 = obj.lock(num,user)
# param_2 = obj.unlock(num,user)
# param_3 = obj.upgrade(num,user)

class LockingTree:

    def __init__(self, parent: List[int]):
        

    def lock(self, num: int, user: int) -> bool:
        

    def unlock(self, num: int, user: int) -> bool:
        

    def upgrade(self, num: int, user: int) -> bool:
        


# Your LockingTree object will be instantiated and called as such:
# obj = LockingTree(parent)
# param_1 = obj.lock(num,user)
# param_2 = obj.unlock(num,user)
# param_3 = obj.upgrade(num,user)