please explain in deatil i dont understand anything like in depth i should understand everythign at once go into depth use illustrations like become the best teacher
"""
# Question 1: Locking the Tree of Space
# You have a world map represented as an M-Ary tree (sample tree below):

# You need to define three operations on it:
# lock(X, uid)
# unlock(X, uid)
# upgradeLock(X, uid)
# Where X is the name of a node in the tree (which is unique), and uid is the user performing the operation.
# Definitions for the Operations:
# Lock(X, uid):
# Lock takes exclusive access on the subtree rooted at X. Once lock(X, uid) succeeds:
# lock(A, anyUserId) should fail (returns false), where A is a descendant of X.
# lock(B, anyUserId) should fail (returns false), where X is a descendant of B.
# Lock operation cannot be performed on a node that is already locked, i.e., lock(X, anyUserId) should fail (returns false).
# Unlock(X, uid):
# Unlock reverts what was done by the lock operation. It can only be called on the same node on which user uid had called a lock before. Returns true if successful.
# UpgradeLock(X, uid):
# This helps the user uid upgrade their lock to an ancestor node. It is only possible if the node X already has locked descendants and all of them are locked by the same user uid. Upgrade should fail if there is any node which is a descendant of X that is locked by a different user. A successful upgrade will "lock" the node. UpgradeLock must not violate the consistency model required by Lock/Unlock.
# Notes:
# The number of nodes in the tree, N, is very large, so optimize the time complexity for the above algorithms.
# Input Format:
# The first line contains the number of nodes in the tree (N).
# The second line contains the number of children per node (m in an m-ary tree).
# The third line contains the number of queries (Q).
# Next N lines contain the NodeName (string) in the m-Ary Tree.
# The next Q lines contain queries in the format: OperationType NodeName UserId.
# Operation Type:
# 1 for Lock
# 2 for Unlock
# 3 for UpgradeLock
# NodeName: The name of any node (unique) in the m-Ary Tree.
# UserId: An integer representing a unique user.
# Example Input:
# 7
# 2
# 3
# World
# Asia
# Africa
# China
# India
# South Africa
# Egypt
# 1 China 9
# 2 India 9
# 3 Asia 9


# This input represents a 2-ary tree with 7 nodes as follows:
#            World
#            /     \
#       Asia        Africa
#      /    \       /     \
#  China  India  South Africa  Egypt


# Additional Notes:
# The tree is always fully balanced.
# Constraints:
# (1 < N < 5 \times 10^5)
# (1 < m < 30)
# (1 < Q < 5 \times 10^5)
# (1 < \text{length of NodeName} < 20)
# Optimize the time complexity:
# Lock: (O(\log_m N))
# Unlock: (O(\log_m N))
# UpgradeLock: (O(\text{numberOfLockedNodes} \times \log_m N))
# The lock operation on an already locked node should fail.
# Once UpgradeLock(X, uid) succeeds on X, it is equivalent to X being locked by uid. As per the definition, Lock(A/B, anyUser) should fail, and Unlock(X, uid) should also work.
# Upgrade lock operation on a node having no locked descendants should fail, and upgrade lock on an already locked node should also fail.


import math

class Node:
    def __init__(self, val):
        self.val = val
        self.uid = None
        self.parent = None
        self.children = []
        self.isLocked = False
        self.isDescendantLocked = 0
        
class Tree:
    def __init__(self, n, m, node_lst, queries):
        self.node_lst = []
        self.node_map = {}
        for node in node_lst:
            converted = Node(node)
            self.node_lst.append(converted)
            self.node_map[node] = converted
            
        for i in range(int(n/m)):
            start = i*m + 1
            end = i*m + m
            if end > n-1:
                end -= end%(n-1)
            if end < n:
                self.node_lst[i].children = self.node_lst[start: end+1]
            
        for i in range(1, n):
            self.node_lst[i].parent = self.node_lst[math.ceil(i/m) - 1]

        self.root = self.node_lst[0]
        self.processed_queries = [query.split() for query in queries]
    
    def lock(self, node, uid):
        if node.isDescendantLocked>0 or node.isLocked or self.isAncestorLocked(node.parent):
            return False
        
        node.uid = uid
        node.isLocked = True
        parent_node = node.parent
        
        while parent_node:
            parent_node.isDescendantLocked += 1
            parent_node = parent_node.parent
        return True
        
    def unlock(self, node, uid):
        if uid != node.uid or not node.isLocked:
            return False
        node.isLocked = False
        node.uid = None
        parent_node = node.parent
        
        while parent_node:
            parent_node.isDescendantLocked -= 1
            parent_node = parent_node.parent
        return True
        
    def upgrade(self, node, uid):
        if node.isDescendantLocked == 0 or self.isAncestorLocked(node.parent):
            return False
            
        self.unlockChildren(node, uid)
        self.lock(node, uid)
        
        return True
        
    def isAncestorLocked(self, node):
        while node:
            if node.isLocked:
                return True
            node = node.parent
        return False
        
        
    def unlockChildren(self, node, uid):
        for child in node.children:
            self.unlock(child, uid)
            self.unlockChildren(child, uid)
        
    def __print_tree(self, node, out):
        out += node.val + " No of Descendants Locked: " + str(node.isDescendantLocked) + " is Node Locked: " + str(node.isLocked) + ",\n"
        for child in node.children:
            out = self.__print_tree(child, out)
        return out
        
    def __str__(self):
        return self.__print_tree(self.root, "")

n = 7 # no of nodes
m = 2 # To create m-ary tree
nodes = ["World", "Asia", "Africa", "China", "India", "SouthAfrica", "Egypt"]
queries = ["1 China 9", "1 India 9", "3 Asia 9", "2 India 9", "2 Asia 9"]
obj = Tree(n, m, nodes, queries)

res = []

for query in obj.processed_queries:
    if query[0] == "1":
        res.append(obj.lock(obj.node_map[query[1]], query[2]))
    elif query[0] == "2":
        res.append(obj.unlock(obj.node_map[query[1]], query[2]))
    elif query[0] == "3":
        res.append(obj.upgrade(obj.node_map[query[1]], query[2]))

print(res)

"""