["LockingTree","upgrade","upgrade","upgrade","upgrade","unlock","unlock","upgrade","upgrade","upgrade","lock","lock","upgrade","upgrade","unlock","upgrade","upgrade","upgrade","upgrade","unlock","unlock"] [[[-1,6,5,5,7,0,7,0,0,6]],[5,3],[2,3],[7,39],[1,32],[5,44],[2,15],[1,11],[1,18],[3,7],[5,36],[5,42],[8,5],[1,19],[3,38],[0,27],[4,11],[9,2],[8…

operations-on-tree-1993.py

# You are given a tree with n nodes numbered from 0 to n - 1 in the form of a 
# parent array parent where parent[i] is the parent of the iᵗʰ node. The root of 
# the tree is node 0, so parent[0] = -1 since it has no parent. You want to design a 
# data structure that allows users to lock, unlock, and upgrade nodes in the tree.
#  
# 
#  The data structure should support the following functions: 
# 
#  
#  Lock: Locks the given node for the given user and prevents other users from 
# locking the same node. You may only lock a node if the node is unlocked. 
#  Unlock: Unlocks the given node for the given user. You may only unlock a 
# node if it is currently locked by the same user. 
#  Upgrade: Locks the given node for the given user and unlocks all of its 
# descendants. You may only upgrade a node if all 3 conditions are true:
#  
#  The node is unlocked, 
#  It has at least one locked descendant (by any user), and 
#  It does not have any locked ancestors. 
#  
#  
#  
# 
#  Implement the LockingTree class: 
# 
#  
#  LockingTree(int[] parent) initializes the data structure with the parent 
# array. 
#  lock(int num, int user) returns true if it is possible for the user with id 
# user to lock the node num, or false otherwise. If it is possible, the node num 
# will become locked by the user with id user. 
#  unlock(int num, int user) returns true if it is possible for the user with 
# id user to unlock the node num, or false otherwise. If it is possible, the node 
# num will become unlocked. 
#  upgrade(int num, int user) returns true if it is possible for the user with 
# id user to upgrade the node num, or false otherwise. If it is possible, the node 
# num will be upgraded. 
#  
# 
#  
#  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]
# 
# 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.
#  
# 
#  
#  Constraints: 
# 
#  
#  n == parent.length 
#  2 <= n <= 2000 
#  0 <= parent[i] <= n - 1 for i != 0 
#  parent[0] == -1 
#  0 <= num <= n - 1 
#  1 <= user <= 10⁴ 
#  parent represents a valid tree. 
#  At most 2000 calls in total will be made to lock, unlock, and upgrade. 
#  
#  👍 97 👎 23

# 2021-09-06 13:38:05
import collections
from typing import List
# leetcode submit region begin(Prohibit modification and deletion)
class LockingTree:

    def __init__(self, parent: List[int]):
        self.parent = parent
        self.locks = [0] * len(parent)
        self.children = collections.defaultdict(set)
        for i in range(len(parent)):
            if parent[i] != -1:
                self.children[parent[i]].add(i)


    def lock(self, num: int, user: int) -> bool:
        if not self.locks[num]:
            self.locks[num] = user
            return True
        return False
        

    def unlock(self, num: int, user: int) -> bool:
        if self.locks[num] == user:
            self.locks[num] = 0
            return True
        return False

    # also checked node itself
    def _is_ancestor_locked(self, num):
        while num != -1:
            if self.locks[num]:
                return True
            num = self.parent[num]

    def _is_descent_looked(self,num):
        que = collections.deque([num])
        while que:
            node = que.popleft()
            if self.locks[node]:
                return True
            for k in self.children[node]:
                que.append(k)
        return False

    def upgrade(self, num: int, user: int) -> bool:
        if self._is_ancestor_locked(num):
            return False
        if not self._is_descent_looked(num):
            return False

        self.locks[num] = user
        return True

# 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)
# leetcode submit region end(Prohibit modification and deletion)

["LockingTree","upgrade","upgrade","upgrade","upgrade","unlock","unlock","upgrade","upgrade","upgrade","lock","lock","upgrade","upgrade","unlock","upgrade","upgrade","upgrade","upgrade","unlock","unlock"]
[[[-1,6,5,5,7,0,7,0,0,6]],[5,3],[2,3],[7,39],[1,32],[5,44],[2,15],[1,11],[1,18],[3,7],[5,36],[5,42],[8,5],[1,19],[3,38],[0,27],[4,11],[9,2],[8,41],[5,36],[7,29]]