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 ith 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 using this function if the node is unlocked.
	Unlock: Unlocks the given node for the given user. You may only unlock a node using this function if it is currently locked by the same user.
	Upgrade: Locks the given node for the given user and unlocks all of its descendants regardless of who locked it. 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.


&nbsp;
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.


&nbsp;
Constraints:


	n == parent.length
	2 &lt;= n &lt;= 2000
	0 &lt;= parent[i] &lt;= n - 1 for i != 0
	parent[0] == -1
	0 &lt;= num &lt;= n - 1
	1 &lt;= user &lt;= 104
	parent represents a valid tree.
	At most 2000 calls in total will be made to lock, unlock, and upgrade.


class LockingTree:

    def __init__(self, parent: List[int]):
        self.p = collections.defaultdict(lambda: -2)
        self.c = collections.defaultdict(list)
        for i, p in enumerate(parent):
            self.c[p].append(i)
            self.p[i] = p
        self.user = collections.defaultdict(set)
        self.node = collections.defaultdict(lambda: -2)

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

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

    def upgrade(self, num: int, user: int) -> bool:
        if self.node[num] != -2: return False
        if not self.has_locked_descendant(num): return False
        if self.has_locked_ancester(num): return False
        self.lock(num, user)
        self.unlock_descendant(num)
        return True
    
    def has_locked_descendant(self, num):  #function to check if alteast one desendent is lock or not 
        has = False
        for child in self.c[num]:
            if self.node[child] != -2:
                return True
            has |= self.has_locked_descendant(child)
        return has               
        
    def has_locked_ancester(self, num):   # function to check if no parent is locked 
        if num == -1: return False
        if self.node[self.p[num]] != -2:
            return True
        return self.has_locked_ancester(self.p[num])

    def unlock_descendant(self, num):   # function fro unlocking all desendents 
        for child in self.c[num]:
            if child in self.node:
                user = self.node[child]
                del self.node[child]
                if user in self.user:
                    self.user[user].remove(child)
            self.unlock_descendant(child)
class LockingTree {
    int[] p;
    Map<Integer, Integer> map = new HashMap<>();
    Map<Integer, List<Integer>> children = new HashMap<>();
    public LockingTree(int[] parent) {
        p = parent;
        for(int i = 0; i < p.length; i ++) {
            children.put(i, new ArrayList<>());
        }
        for(int i = 1; i < p.length; i ++) {
            children.get(p[i]).add(i);
        }
    }
    
    public boolean lock(int num, int user) {
        if(!map.containsKey(num)) {
            map.put(num, user);
            return true;
        } 
        return false;
    }
    
    public boolean unlock(int num, int user) {
        if(map.containsKey(num) && map.get(num) == user) {
            map.remove(num);
            return true;
        }
        return false;
    }
    
    public boolean upgrade(int num, int user) {
        //check the node
        if(map.containsKey(num)) return false;
        //check Ancestor
        int ori = num;
        while(p[num] != -1) {
            if(map.get(p[num]) != null) return false;
            num = p[num];
        }
        //check Decendant
        Queue<Integer> q = new LinkedList<>();
        List<Integer> child = children.get(ori);
        if(child != null) {
            for(int c : child) q.offer(c);
        }
        boolean lock = false;
        while(!q.isEmpty()) {
            int cur = q.poll();
            if(map.get(cur) != null) {
                lock = true;
                map.remove(cur); // unlock
            }
            List<Integer> cc = children.get(cur);
            if(cc != null) {
                for(int c : cc) q.offer(c);
            }
        }        
        if(!lock) return false;
        map.put(ori, user); // lock the original node
        return true;
    }
}
class LockingTree {
public:
    
    unordered_map<int,int> locks_aquired;
    vector<vector<int>> graph;
    unordered_map<int,int> parents;
    
    LockingTree(vector<int>& parent)
    {   
        int n=parent.size();
        graph =  vector<vector<int> >(n);
        parents[0] = -1 ;   // since parent of node 0 is always -1 

        for(int i=1; i<n; i++)
        {
            parents[i] = parent[i];  
            graph[parent[i]].push_back(i);
        }
    }
     
    bool lock(int num, int user)    
    {
        if(locks_aquired.find(num) == locks_aquired.end())
            { locks_aquired[num]=user; return 1;}
        return 0;
    }
    
    
    bool unlock(int num, int user)      
    {
        if(locks_aquired.find(num) != locks_aquired.end() && locks_aquired[num]==user)
            {   locks_aquired.erase(num); return 1;}
        return 0;
    }
    
    bool check_ans(int num)
    {
        while(num != -1)
        {
            if(locks_aquired.find(num) != locks_aquired.end()) return 0;
            num = parents[num];   
        }
        return 1;
    }
    
    bool dfs(int num)   // function to check if alteast one desendent is lock or not 
    {
        for(int i=0; i<graph[num].size(); i++)
        {
            int x = graph[num][i]; 
            if( locks_aquired.find(x) != locks_aquired.end())
                return 1;
            if( dfs(x)) return 1;
        }
        return 0; 
    }
    
    void unlock_descendents(int num)   
    {
        for(int i=0; i<graph[num].size(); i++)
        {
            int x = graph[num][i]; 
            if( locks_aquired.find(x) != locks_aquired.end())
                locks_aquired.erase(x);
            dfs_des(x);
        }
    }
    
    bool upgrade(int num, int user) 
    {   
        if( locks_aquired.find(num) != locks_aquired.end()) return 0;     // if current node is locked can't lock it again 
        
        if( dfs(num) && check_ans(parents[num]))  
        {
            unlock_descendents(num); 
            locks_aquired[num]=user;
            return 1;
        }
        return 0;
    }
};

/**
 * Your LockingTree object will be instantiated and called as such:
 * LockingTree* obj = new LockingTree(parent);
 * bool param_1 = obj->lock(num,user);
 * bool param_2 = obj->unlock(num,user);
 * bool param_3 = obj->upgrade(num,user);
 */
var LockingTree = function(parent) {
    this.parents = parent;
    this.children  = [];
    this.locked = new Map();
    
    for (let i = 0; i < this.parents.length; ++i) {
        this.children[i] = [];
    }
    
    for (let i = 1; i < this.parents.length; ++i) {
        const parent = this.parents[i];
        
        this.children[parent].push(i);
    }
};

LockingTree.prototype.lock = function(num, user) {
    if (this.locked.has(num)) return false;

    this.locked.set(num, user);
   
    return true;
};

LockingTree.prototype.unlock = function(num, user) {
    if (!this.locked.has(num) || this.locked.get(num) != user) return false;
    
    this.locked.delete(num);
    
    return true;
};

LockingTree.prototype.upgrade = function(num, user) {
    let isLocked = traverseUp(num, this.parents, this.locked);

    if (isLocked) return false;

    const queue = [];

    isLocked = false;

    queue.push(num);

    while (queue.length > 0) {
        const node = queue.shift();

        if (node != num && this.locked.has(node)) {
            isLocked = true;
            this.locked.delete(node);
        }

        for (let i = 0; i < this.children[node].length; ++i) {
            queue.push(this.children[node][i]);
        }
    } 

    if (!isLocked) return false;

    this.locked.set(num, user);

    return true;


    function traverseUp(num, parents, locked) {
        if (locked.has(num)) return true;
        if (num === 0) return false;

        const parentIdx = parents[num];

        return traverseUp(parentIdx, parents, locked);
    }
};
Operations on Tree