what is the timecomplexxity like will it pas this questions 
Problem statement
You are given a complete, balanced M-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
P.S. - The question was very badly stated and not a single constraint was mentioned openly on the problem statement. A lot of these constraints had to be deduced by supplying custom input and observing the expected output. There were no constraints on the size of the variables.

anotjer version 
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.

i wanted to know if either of these will pass the ps with hitting tle 

"""
import sys

class Node:
    def __init__(self, val):
        self.val = val
        self.uid = None
        self.parent = None  
        self.child = [] 
        self.isLocked = False  
        self.locked_descendants = set()  # Set of locked descendant nodes

class Tree:
    def __init__(self, m, n, name_list):
        self.node_list = []
        self.node_map = {}
        for name in name_list:
            node = Node(name)
            self.node_list.append(node)
            self.node_map[name] = node

        # Build the tree
        for i in range(n):
            for j in range(m):
                child_index = m * i + j + 1
                if child_index < n:
                    self.node_list[i].child.append(self.node_list[child_index])
                    self.node_list[child_index].parent = self.node_list[i]

        self.root = self.node_list[0]

    def lock(self, node, uid):
        if node.isLocked:
            return False

        # Check if any ancestor is locked
        current = node.parent
        while current:
            if current.isLocked:
                return False
            current = current.parent

        # Check if any descendant is locked
        if node.locked_descendants:
            return False

        # Lock the node
        node.isLocked = True
        node.uid = uid

        # Update locked_descendants for all ancestors
        current = node.parent
        while current:
            current.locked_descendants.add(node)
            current = current.parent

        return True

    def unlock(self, node, uid):
        if not node.isLocked or node.uid != uid:
            return False

        # Unlock the node
        node.isLocked = False
        node.uid = None

        # Update locked_descendants for all ancestors
        current = node.parent
        while current:
            current.locked_descendants.discard(node)  # Correct
            current = current.parent

        return True

    def upgrade(self, node, uid):
        if node.isLocked:
            return False

        # Check if any ancestor is locked
        current = node.parent
        while current:
            if current.isLocked:
                return False
            current = current.parent

        # Check if there is at least one locked descendant
        if not node.locked_descendants:
            return False

        # Collect all locked descendants
        locked_descendants = list(node.locked_descendants)

        # Check if all locked descendants have the same uid
        for ld in locked_descendants:
            if ld.uid != uid:
                return False

        # Unlock all locked descendants
        for ld in locked_descendants:
            ld.isLocked = False
            ld.uid = None
            node.locked_descendants.discard(ld)

            # Update locked_descendants for all ancestors of ld
            ancestor = ld.parent
            while ancestor:
                ancestor.locked_descendants.discard(ld)
                ancestor = ancestor.parent

        # Lock the current node
        node.isLocked = True
        node.uid = uid

        # Update locked_descendants for all ancestors
        current = node.parent
        while current:
            current.locked_descendants.add(node)
            current = current.parent

        return True

    def process_queries(self, queries):
        results = []
        for query in queries:
            parts = query.strip().split()
            if len(parts) != 3:
                results.append('false')
                continue
            operation, node_name, uid = parts
            uid = int(uid)
            node = self.node_map.get(node_name, None)
            if not node:
                results.append('false')
                continue
            if operation == "1":
                result = self.lock(node, uid)
            elif operation == "2":
                result = self.unlock(node, uid)
            elif operation == "3":
                result = self.upgrade(node, uid)
            else:
                result = False  # Invalid operation
            results.append('true' if result else 'false')
        return results

def main():
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    q = int(sys.stdin.readline())
    name_list = [sys.stdin.readline().strip() for _ in range(n)]
    queries = [sys.stdin.readline().strip() for _ in range(q)]
    tree = Tree(m, n, name_list)
    results = tree.process_queries(queries)
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

"""
2
"""
import sys

class Node:
    def __init__(self, val):
        self.val = val
        self.uid = None
        self.parent = None  
        self.child = [] 
        self.isLocked = False  
        self.lockedDescendantCount = 0  
        # For Euler Tour
        self.in_time = 0
        self.out_time = 0

class Tree:
    def __init__(self, m, n, name_list):
        self.node_list = []
        self.node_map = {}
        for name in name_list:
            node = Node(name)
            self.node_list.append(node)
            self.node_map[name] = node

        # Build the tree
        for i in range(n):
            for j in range(m):
                child_index = m * i + j + 1
                if child_index < n:
                    self.node_list[i].child.append(self.node_list[child_index])
                    self.node_list[child_index].parent = self.node_list[i]

        self.root = self.node_list[0]

        # Initialize Euler Tour
        self.time = 1
        self.euler_tour(self.root)

        # Global set of locked nodes
        self.locked_nodes = set()

    def euler_tour(self, node):
        node.in_time = self.time
        self.time += 1
        for child in node.child:
            self.euler_tour(child)
        node.out_time = self.time
        self.time += 1

    def is_descendant(self, ancestor, node):
        return ancestor.in_time < node.in_time and node.out_time < ancestor.out_time

    def lock(self, node, uid):
        if node.isLocked:
            return False

        # Check if any ancestor is locked
        current = node.parent
        while current:
            if current.isLocked:
                return False
            current = current.parent

        # Check if any descendant is locked
        if node.lockedDescendantCount > 0:
            return False

        # Lock the node
        node.isLocked = True
        node.uid = uid
        self.locked_nodes.add(node)

        # Update the lockedDescendantCount for ancestors
        parent = node.parent
        while parent:
            parent.lockedDescendantCount += 1
            parent = parent.parent

        return True

    def unlock(self, node, uid):
        if not node.isLocked or node.uid != uid:
            return False

        # Unlock the node
        node.isLocked = False
        node.uid = None
        self.locked_nodes.remove(node)

        # Update the lockedDescendantCount for ancestors
        parent = node.parent
        while parent:
            parent.lockedDescendantCount -= 1
            parent = parent.parent

        return True

    def upgrade(self, node, uid):
        if node.isLocked:
            return False

        # Check if any ancestor is locked
        current = node.parent
        while current:
            if current.isLocked:
                return False
            current = current.parent

        if node.lockedDescendantCount == 0:
            return False

        # Collect all locked descendants using the global set and Euler Tour
        locked_descendants = [locked_node for locked_node in self.locked_nodes if self.is_descendant(node, locked_node)]

        if not locked_descendants:
            return False

        # Check if all locked descendants have the same uid
        for ld in locked_descendants:
            if ld.uid != uid:
                return False

        # Unlock all locked descendants
        for ld in locked_descendants:
            ld.isLocked = False
            ld.uid = None
            self.locked_nodes.remove(ld)

            # Update the lockedDescendantCount for ancestors
            parent = ld.parent
            while parent:
                parent.lockedDescendantCount -= 1
                parent = parent.parent

        # Lock the current node
        node.isLocked = True
        node.uid = uid
        self.locked_nodes.add(node)

        # Update the lockedDescendantCount for ancestors
        parent = node.parent
        while parent:
            parent.lockedDescendantCount += 1
            parent = parent.parent

        return True

    def process_queries(self, queries):
        results = []
        for query in queries:
            parts = query.strip().split()
            if len(parts) != 3:
                results.append('false')
                continue
            operation, node_name, uid = parts
            uid = int(uid)
            node = self.node_map.get(node_name, None)
            if not node:
                results.append('false')
                continue
            if operation == "1":
                result = self.lock(node, uid)
            elif operation == "2":
                result = self.unlock(node, uid)
            elif operation == "3":
                result = self.upgrade(node, uid)
            else:
                result = False  # Invalid operation
            results.append('true' if result else 'false')
        return results

def main():
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    q = int(sys.stdin.readline())
    name_list = [sys.stdin.readline().strip() for _ in range(n)]
    queries = [sys.stdin.readline().strip() for _ in range(q)]
    tree = Tree(m, n, name_list)
    results = tree.process_queries(queries)
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

"""