please fix my code and give complete correct code why fail explai nall 
""
# **Locking The Tree of Space**

You have a world map represented as an M-Ary tree (sample tree below)  

<aside>

<img src="./images/asterisk_green.svg" alt="asterisk_green.svg" width="15px" /> In graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary or k-way tree) is an arborescence (or an ordered tree) in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three.

<img src="./images/asterisk_green.svg" alt="asterisk_green.svg" width="15px" /> In graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. A graph is a collection of vertices (also known as nodes) and edges that connect these vertices. A tree is a special type of graph that is connected and acyclic, meaning that there are no cycles in the graph. In a tree, there is a unique path between any two vertices, and there is a single vertex called the root that is used as the starting point for traversing the tree. 

</aside>

![Sample Tree](./images/Sample%20Tree.png)

You need to define three operations on it:

```cpp
1. lock(X, uid)
2. unlock(X, uid)
3. upgradeLock(X, uid)
```

where `X` the name of a node in the tree (that would be unique) and `uid` is the user who is performing the operation.  
**Input format**: x is country name (string) and uid is user number (number).

**Here are the definitions for the operations:**

>**`lock(x, uid)`**  
Lock takes an exclusive access on the subtree rooted at `X`. It is formally defined like this: Once `lock(x, uid)` succeeds, then:  
    <li>`lock(A, anyUserid)` should fail (returns false), where `A` is a descendent of `X`,</li>
    <li>`lock(B, anyUserld)` should fail (returns false), where `X` is a descendent of `B`,</li>
    <li>Lock operation cannot be performed on a node which is already locked i.e. `lock(x, anyUserld)` should fail (returns false).</li>  
    <aside>
    <img src="./images/asterisk_green.svg" alt="asterisk_green.svg" width="15px" /> Exclusive access means that only one user can lock a node and its descendants at a time, and no other user can lock any node that is related to the locked node by ancestry or descent. This ensures that there is no conflict or interference between different users who want to perform operations on the tree.
    </aside> 

>**`unlock(X, uid)`**  
Unlock reverts what was done by the lock operation. It can only be called on same node on which user `uid` had called a Lock on before. Returns true if it is successful.

>**`upgradeLock(x, uid)`**  
It 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 only locked by the same user `uid`. Upgrade should fail if there is any node which is descendant of X that is locked by a different user. Successful Upgrade will 'lock' the node. `upgradeLock` call shouldn't violate the consistency model that Lock/Unlock function requires.

**Notes**

1. The number of nodes in the tree `N` is very large. So, optimize the time complexity for the above algorithms.
2. The below section contains the input format.
    - The first line contains the **number** of Nodes in the tree (`N`).
    - The second line contains **number** of children per node (value `m` in m-ary Tree).
    - The third line contains **number** of queries (`Q`).
    - Next **`N`** lines contains the **`NodeName`** (string) in the m-Ary Tree.
    - Next **`Q`** lines contains queries which are in format: 
    **`Operation Type` `NodeName` `Userld`**
    - **Operation Type**
        
        `1` for lock  
        `2` for unlock  
        `3` for upgradeLock
        
    - **`NodeName`** - Name of any node (unique) in m-Ary Tree.
    - **`Userld`** - Integer value representing a unique user.

**Example input**

```cpp
7
2
3
World
Asia
Africa
China
India
South Africa
Egypt
1 China 9
2 India 9
3 Asia 9
```

With the above input you represent a 2-ary tree with 7 nodes as follows:

```
                 World
            /             \
        Asia               Africa
      /      \          /         \
China    India    South Africa   Egypt
```

**Additional Notes**

1. Here `1 China 3` indicates the following '`Operation Type` `NodeName` `Userld`'.
2. The tree is always fully balanced.
3. Constraints on the inputs are as follows:  
1 < **N** < 5 * 10^5  
1 < **m** < 30  
1 < **Q** <5 * 10^5  
1 < length of **NodeName** < 20
4. Optimize the time complexity:
    - Lock - O(logmN)
    - Unlock - O(logmN)
    - UpgradeLock - O(numberOfLockedNodes * logmN)
5. Lock operation on already locked node should fail.
6. Once Upgrade lock(X, uid) succeeds on X. It is equivalent to X being locked by uid. So, Lock(A/B, anyuser) should fail as per the definition of Lock and Unlock(X, uid) should also work.
7. Upgrade lock operation on a node having no locked descendants should fail and upgrade lock on already locked node should also fail.

**Example input**

```cpp
7
2
5
World
Asia
Africa
China
India
SouthAfrica
Egypt
1 China 9
1 India 9
3 Asia 9
2 India 9
2 Asia 9
```

**Example input**

```cpp
true
true
true
false
true
```

Query 1: `1 China 9` ⇒ This operation is success as initially China is unlocked. 

Query 2: `1 India 9` ⇒ This should be success as none of ancestors and descendants of India are locked.

Query 3: `3 Asia 9` ⇒ This also should be success as upgrade operation is done by same user who has locked descendants.

Query 4: `2 India 9` ⇒ This should fail as the India is now not locked 

Query 5: `2 Asia 9` ⇒ This should be success as Asia was earlier (refer Query 3) locked by user 9.
"""
"""
import sys
import io
import contextlib

# The code to be tested (your solution)
code_to_test = '''
from collections import defaultdict
import sys

class Node:
    def __init__(self, name):
        self.name = name
        self.user_id = None                 # ID of the user who locked the node
        self.parent = None                  # Parent node
        self.children = []                  # List of child nodes
        self.is_locked = False              # Lock status of the node
        self.locked_descendant_count = 0    # Number of locked descendants
        self.in_time = 0                    # Entry time during DFS traversal
        self.out_time = 0                   # Exit time during DFS traversal

class Tree:
    def __init__(self, n, m, name_list, queries):
        self.node_list = []
        self.node_map = {}  # Map from node name to Node object

        # Create nodes and map their names
        for name in name_list:
            node = Node(name)
            self.node_list.append(node)
            self.node_map[name] = node

        # Build the tree
        # Adjusted the tree building logic to correctly create the m-ary tree
        for i in range(n):
            parent = self.node_list[i]
            first_child_index = m * i + 1
            for j in range(m):
                child_index = first_child_index + j
                if child_index < n:
                    child = self.node_list[child_index]
                    parent.children.append(child)
                    child.parent = parent
                else:
                    break

        self.root = self.node_list[0]
        self.user_locked_nodes = defaultdict(set)
        self.assign_time(self.root, [0])  # Preprocess for ancestry checks

        # Process queries
        self.processed_queries = []
        for query in queries:
            self.processed_queries.append(query.strip().split())

    def assign_time(self, node, time):
        # Assign entry time (in_time)
        node.in_time = time[0]
        time[0] += 1

        for child in node.children:
            self.assign_time(child, time)

        # Assign exit time (out_time)
        node.out_time = time[0]
        time[0] += 1

    def lock(self, node, user_id):
        # If the node is already locked, return False
        if node.is_locked:
            return False

        # If any ancestors are locked, cannot lock this node
        if self.is_ancestor_locked(node):
            return False

        # If any descendants are locked, cannot lock this node
        if node.locked_descendant_count > 0:
            return False

        # Lock the node
        node.is_locked = True
        node.user_id = user_id
        self.user_locked_nodes[user_id].add(node)

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

        return True

    def unlock(self, node, user_id):
        # The node must be locked and the user_id must match
        if not node.is_locked or node.user_id != user_id:
            return False

        # Unlock the node
        node.is_locked = False
        node.user_id = None
        self.user_locked_nodes[user_id].remove(node)

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

        return True

    def upgrade(self, node, user_id):
        # The node must not be locked
        if node.is_locked:
            return False

        # If any ancestors are locked, cannot upgrade this node
        if self.is_ancestor_locked(node):
            return False

        # The node must have at least one locked descendant
        if node.locked_descendant_count == 0:
            return False

        # Collect locked descendants locked by user_id
        locked_descendants = []
        self.collect_locked_descendants(node, user_id, locked_descendants)

        # All locked descendants under node must be locked by user_id
        if node.locked_descendant_count != len(locked_descendants):
            return False

        # Unlock all locked descendants
        for descendant in locked_descendants:
            descendant.is_locked = False
            descendant.user_id = None
            self.user_locked_nodes[user_id].remove(descendant)

            # Update the locked_descendant_count for ancestors
            parent = descendant.parent
            while parent:
                parent.locked_descendant_count -= 1
                parent = parent.parent

        # Lock the current node
        node.is_locked = True
        node.user_id = user_id
        self.user_locked_nodes[user_id].add(node)

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

        return True

    def collect_locked_descendants(self, node, user_id, locked_descendants):
        for child in node.children:
            if child.is_locked:
                if child.user_id == user_id:
                    locked_descendants.append(child)
                else:
                    return  # Found a locked node by another user
            elif child.locked_descendant_count > 0:
                self.collect_locked_descendants(child, user_id, locked_descendants)

    def is_ancestor_locked(self, node):
        current = node.parent
        while current:
            if current.is_locked:
                return True
            current = current.parent
        return False

    def is_descendant(self, child_node, ancestor_node):
        # Check if child_node is a descendant of ancestor_node
        return (ancestor_node.in_time <= child_node.in_time <= child_node.out_time <= ancestor_node.out_time)

    def process_queries(self):
        results = []
        for query in self.processed_queries:
            operation_type, node_name, user_id = query
            node = self.node_map[node_name]
            user_id = int(user_id)
            if operation_type == "1":
                result = self.lock(node, user_id)
            elif operation_type == "2":
                result = self.unlock(node, user_id)
            elif operation_type == "3":
                result = self.upgrade(node, user_id)
            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())

    node_list = []
    for _ in range(n):
        node_list.append(sys.stdin.readline().strip())

    queries = []
    for _ in range(q):
        queries.append(sys.stdin.readline().strip())

    tree = Tree(n, m, node_list, queries)
    results = tree.process_queries()
    for res in results:
        print(res)
main()
'''

# List of test cases
test_cases = [
    {
        "description": "Test Case 1: Locking a Node When an Ancestor is Locked",
        "input": """7
2
2
World
Asia
Africa
China
India
SouthAfrica
Egypt
1 Asia 1
1 China 2
""",
        "expected_output": """true
false
"""
    },
    {
        "description": "Test Case 2: Locking a Node When a Descendant is Locked",
        "input": """7
2
2
World
Asia
Africa
China
India
SouthAfrica
Egypt
1 India 1
1 Asia 2
""",
        "expected_output": """true
false
"""
    },
    {
        "description": "Test Case 3: Unlocking a Node Locked by Another User",
        "input": """3
2
2
Root
Child1
Child2
1 Child1 1
2 Child1 2
""",
        "expected_output": """true
false
"""
    },
    {
        "description": "Test Case 4: Unlocking a Node That Is Not Locked",
        "input": """3
2
1
Root
Child1
Child2
2 Child1 1
""",
        "expected_output": """false
"""
    },
    {
        "description": "Test Case 5: Upgrade Lock on an Already Locked Node",
        "input": """3
2
2
Root
Child1
Child2
1 Root 1
3 Root 1
""",
        "expected_output": """true
false
"""
    },
    {
        "description": "Test Case 6: Upgrade Lock with No Locked Descendants",
        "input": """3
2
1
Root
Child1
Child2
3 Root 1
""",
        "expected_output": """false
"""
    },
    {
        "description": "Test Case 7: Upgrade Lock When Not All Descendants Are Locked by the Same User",
        "input": """7
2
3
World
Asia
Africa
China
India
SouthAfrica
Egypt
1 China 1
1 India 2
3 Asia 1
""",
        "expected_output": """true
true
false
"""
    },
    {
        "description": "Test Case 8: Successful Lock Operation with No Conflicts",
        "input": """3
2
1
Root
Child1
Child2
1 Child1 1
""",
        "expected_output": """true
"""
    },
    {
        "description": "Test Case 9: Unlocking a Node That Has Been Upgraded",
        "input": """7
2
5
World
Asia
Africa
China
India
SouthAfrica
Egypt
1 China 9
1 India 9
3 Asia 9
2 India 9
2 Asia 9
""",
        "expected_output": """true
true
true
false
true
"""
    },
    {
        "description": "Test Case 10: Maximum Nodes with Upgrade Lock",
        "input": """15
2
8
Root
A
B
C
D
E
F
G
H
I
J
K
L
M
N
1 H 1
1 I 1
1 J 1
1 K 1
1 L 1
1 M 1
1 N 1
3 Root 1
""",
        "expected_output": """true
true
true
true
true
true
true
true
"""
    },
    {
        "description": "Test Case 11: Unlocking After Upgrade Lock",
        "input": """7
2
5
World
Asia
Africa
China
India
SouthAfrica
Egypt
1 China 9
1 India 9
3 Asia 9
2 China 9
2 Asia 9
""",
        "expected_output": """true
true
true
false
true
"""
    },
    {
        "description": "Test Case 12: Locking an Already Locked Node",
        "input": """3
2
2
Root
Child1
Child2
1 Child1 1
1 Child1 2
""",
        "expected_output": """true
false
"""
    },
    {
        "description": "Test Case 13: Re-locking an Unlocked Node",
        "input": """3
2
3
Root
Child1
Child2
1 Child1 1
2 Child1 1
1 Child1 2
""",
        "expected_output": """true
true
true
"""
    },
    {
        "description": "Test Case 14: Locking Sibling Nodes",
        "input": """3
2
2
Root
Child1
Child2
1 Child1 1
1 Child2 2
""",
        "expected_output": """true
true
"""
    },
    {
        "description": "Test Case 15: Complex Upgrade and Lock Scenario",
        "input": """9
3
10
Root
A
B
C
D
E
F
G
H
1 D 1
1 E 1
1 F 2
3 B 1
1 G 1
3 Root 1
2 Root 1
1 H 2
1 A 2
3 Root 2
""",
        "expected_output": """true
true
true
false
true
false
true
true
true
true
"""
    },
]

# Function to run the test case
def run_test_case(code, test_input):
    # Redirect stdin and stdout
    old_stdin = sys.stdin
    old_stdout = sys.stdout
    sys.stdin = io.StringIO(test_input)
    sys.stdout = io.StringIO()
    namespace = {}
    
    try:
        exec(code, namespace)
        output = sys.stdout.getvalue()
    except Exception as e:
        output = f"Error: {e}"
    finally:
        # Restore stdin and stdout
        sys.stdin = old_stdin
        sys.stdout = old_stdout
    
    return output.strip()

# Main testing function
def test_code_on_test_cases():
    all_passed = True
    for idx, test in enumerate(test_cases, 1):
        print(f"Running {test['description']}")
        output = run_test_case(code_to_test, test['input'])
        expected_output = test['expected_output'].strip()
        if output == expected_output:
            print(f"Test Case {idx} Passed\n")
        else:
            print(f"Test Case {idx} Failed")
            print("Expected Output:")
            print(expected_output)
            print("Actual Output:")
            print(output)
            print()
            all_passed = False
    if all_passed:
        print("All test cases passed!")
    else:
        print("Some test cases failed. Please review your code.")

# Run the tests
test_code_on_test_cases()

"""
"""
(base) asvinir@Asvinis-MacBook-Air learnDsa % /opt/homebrew/bin/python3 "/Users/asvinir/Library/Mobile Documents/com~apple~CloudDocs/Downloads/learnDsa/tree_of_spa
ceAtest.py"
Running Test Case 1: Locking a Node When an Ancestor is Locked
Test Case 1 Passed

Running Test Case 2: Locking a Node When a Descendant is Locked
Test Case 2 Passed

Running Test Case 3: Unlocking a Node Locked by Another User
Test Case 3 Passed

Running Test Case 4: Unlocking a Node That Is Not Locked
Test Case 4 Passed

Running Test Case 5: Upgrade Lock on an Already Locked Node
Test Case 5 Passed

Running Test Case 6: Upgrade Lock with No Locked Descendants
Test Case 6 Passed

Running Test Case 7: Upgrade Lock When Not All Descendants Are Locked by the Same User
Test Case 7 Passed

Running Test Case 8: Successful Lock Operation with No Conflicts
Test Case 8 Passed

Running Test Case 9: Unlocking a Node That Has Been Upgraded
Test Case 9 Passed

Running Test Case 10: Maximum Nodes with Upgrade Lock
Test Case 10 Passed

Running Test Case 11: Unlocking After Upgrade Lock
Test Case 11 Passed

Running Test Case 12: Locking an Already Locked Node
Test Case 12 Passed

Running Test Case 13: Re-locking an Unlocked Node
Test Case 13 Passed

Running Test Case 14: Locking Sibling Nodes
Test Case 14 Passed

Running Test Case 15: Complex Upgrade and Lock Scenario
Test Case 15 Failed
Expected Output:
true
true
true
false
true
false
true
true
true
true
Actual Output:
true
true
true
false
true
false
false
true
false
false

Some test cases failed. Please review your code.
"""