Locking and Unlocking N-Ary Tree

1) Lock(X, uid): This operation attempts to grant an exclusive lock on the node X for the user uid. A lock can only be granted if:
  I) The node X is not already locked.
  II) No ancestor of X is locked.
  III) No descendant of X is locked.

2) Unlock(X, uid): This operation releases a lock on node X. It can only be performed if:
  I) The node X is currently locked.
  II) The lock on X is held by the same user uid.

3) UpgradeLock(X, uid): This operation allows a user uid to lock an ancestor node X by atomically unlocking all of its descendants that they have locked. An upgrade is possible only if:
  I) The node X is not currently locked.
  II) X has at least one locked descendant.
  III) All locked descendants of X are locked by the same user uid.
  IV) If successful, X becomes locked by uid, and all its previously locked descendants become unlocked.

1) The first line contains three space-separated integers: 'N' (number of nodes), 'M' (arity of the tree), and 'Q' (number of queries).
2) The second line contains 'N' space-separated strings, representing the names of the nodes in order from index 0 to N-1. The first node is always the root.
3) The next 'N-1' lines describe the tree structure. Each line contains a parent node name followed by a child node name.
4) The next 'Q' lines contain the queries. Each line is a string in the format: "op_type node_name uid".
  I) op_type: An integer 1 for Lock, 2 for Unlock, 3 for Upgrade.
  II) node_name: The string name of the target node.
  III) uid: The integer user ID.

For each query, print true if the operation was successful, or false if it failed, each on a new line.

Sample Input 1:

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

Sample Output 1:

true
true
true
false
true

Explanation for Sample 1:

1. `1 China 9`: Lock China for user 9. Succeeds as no ancestors or descendants are locked. Output: `true`.
2. `1 India 9`: Lock India for user 9. Succeeds. Output: `true`.
3. `3 Asia 9`: Upgrade lock to Asia for user 9. Succeeds because Asia is unlocked, and its locked descendants (China, India) are all locked by user 9. China and India are now unlocked, and Asia becomes locked. Output: `true`.
4. `2 India 9`: Unlock India. Fails because India is no longer locked (it was unlocked by the upgrade). Output: `false`.
5. `2 Asia 9`: Unlock Asia. Succeeds as it is locked by user 9. Output: `true`.

Sample Input 2:

3 2 2
World China India
World China
World India
3 India 1
1 World 9

Sample Output 2:

false
true

Explanation for Sample 2:

1. `3 India 1`: Upgrade lock to India. Fails because India has no locked descendants. Output: `false`.
2. `1 World 9`: Lock World. Succeeds as the tree is empty. Output: `true`.

Expected Time Complexity:

Lock/Unlock: O(height of the tree)
Upgrade: O(size of the subtree)

Constraints:

1 <= N, Q <= 2000
1 <= M <= N
1 <= uid <= 100
Node names consist of letters and are unique.

Time limit: 1sec