Dado um mapa-múndi na forma de Árvore M-ária Genérica consistindo de N nós e uma array de consultas [] , a tarefa é implementar as funções Bloquear , Desbloquear e Atualizar para a árvore dada. Para cada consulta em queries [] , as funções retornam verdadeiro quando a operação é realizada com sucesso, caso contrário, retorna falso . As funções são definidas como: 

X: Nome do nó na árvore e será único
uid: ID do usuário para a pessoa que acessa o nó X

1. Lock (X, uid): Lock tem acesso exclusivo à subárvore enraizada.

• Depois de bloqueio (X, UID) for bem sucedido, então bloqueio (A, qualquer utilizador) deve falhar, onde A é um descendente de X .
• Lock (B. Qualquer usuário) deve falhar onde X é um descendente de B .
• A operação de bloqueio não pode ser executada em um nó que já está bloqueado.

2. Desbloquear (X, uid): Para desbloquear o nó bloqueado.

• O desbloqueio reverte o que foi feito pela operação de bloqueio .
• Ele só pode ser chamado e desbloqueado pelo mesmo uid .

3. UpgradeLock (X, uid): O usuário uid pode atualizar seu bloqueio para um nó ancestral.

• Só é possível se qualquer nó ancestral estiver bloqueado apenas pelo mesmo uid do usuário .
• A atualização deve cair se houver algum nó que está bloqueado por algum outro uid Y abaixo.

Exemplos:

Entrada: N = 7, M = 2, nodes = ['Mundo', 'Ásia', 'África', 'China', 'Índia', 'África do Sul', 'Egito'],  
consultas = ['1 China 9' , '1 Índia 9', '3 Ásia 9', '2 Índia 9', '2 Ásia 9']
Resultado: verdadeiro verdadeiro verdadeiro falso verdadeiro

Entrada: N = 3, M = 2, nós = ['Mundo', 'China', 'Índia'],  
consultas = ['3 Índia 1', '1 Mundo 9']
Resultado: falso verdadeiro

Abaixo está a implementação da abordagem acima:

# Python Implementation
  
# Locking function
def lock(name):
    ind = nodes.index(name)+1
    c1 = ind * 2
    c2 = ind * 2 + 1
    if status[name] == 'lock' \
            or status[name] == 'fail':
        return 'false'
    else:
        p = ind//2
        status[nodes[p-1]] = 'fail'
        status[name] = 'lock'
        return 'true'
  
# Unlocking function
def unlock(name):
    if status[name] == 'lock':
        status[name] = 'unlock'
        return 'true'
    else:
        return 'false'
  
# Upgrade function
def upgrade(name):
    ind = nodes.index(name)+1
  
    # left child of ind
    c1 = ind * 2
  
    # right child of ind
    c2 = ind * 2 + 1
    if c1 in range(1, n) and c2 in range(1, n):
        if status[nodes[c1-1]] == 'lock' \
            and status[nodes[c2-1]] == 'lock':
            status[nodes[c1-1]] = 'unlock'
            status[nodes[c2-1]] = 'unlock'
            status[nodes[ind-1]] = 'lock'
            return 'true'
        else:
            return 'false'
  
# Precomputation
def precompute(queries):
  d = []
    
  # Traversing the queries
  for j in queries:
      i = j.split()
      d.append(i[1])
      d.append(int(i[0]))
  
  status = {}
  for j in range(0, len(d)-1, 2):
      status[d[j]] = 0
  return status, d
  
# Function to perform operations
def operation(name, code):
    result = 'false'
      
    # Choose operation to perform
    if code == 1:
        result = lock(name)
    elif code == 2:
        result = unlock(name)
    elif code == 3:
        result = upgrade(name)
    return result
    
    
# Driver Code
if __name__ == '__main__':
    
      # Given Input
    n = 7;m = 2
    apis = 5
    nodes = ['World', 'Asia', \
            'Africa', 'China', \
            'India', 'SouthAfrica', 'Egypt']
    queries = ['1 China 9', '1 India 9', \
             '3 Asia 9', '2 India 9', '2 Asia 9']
      
    # Precomputation
    status, d = precompute(queries)
  
    # Function Call
    for j in range(0, len(d) - 1, 2):
        print(operation(d[j], d[j + 1]), end = ' ')

verdadeiro verdadeiro verdadeiro falso verdadeiro

verdadeiro verdadeiro verdadeiro falso verdadeiro 

Complexidade de tempo: O (LogN)
Espaço auxiliar: O (N)