Com abordar aquest problema

Se't donen relacions de parentiu del tipus X HIJO DE Y, i has de saber si dues persones formen part del mateix arbre familiar (encara que la relació sigui llunyana), no només si hi ha una relació directa entre elles.

Idea general:

1. Llegeix el nombre de casos de prova.
2. Per a cada cas, llegeix quantes línies té (relacions + la línia final amb el nom a consultar).
3. Per a cada relació X HIJO DE Y, afegeix una connexió (aresta) entre X i Y en una estructura de graf (per exemple, un diccionari on cada nom apunta a un conjunt dels noms amb qui està directament connectat).
4. Un cop construït el graf d'aquest cas, recorre'l a partir de THOR (amb una cerca en amplada o en profunditat, BFS/DFS) per trobar tots els noms que formen part del seu mateix arbre familiar.
5. Comprova si el nom que es demana és un d'aquests, i escriu SI o NO.
6. Recorda construir un graf nou per a cada cas de prova: les relacions no es mantenen d'un cas a l'altre.

Paranys habituals:

• Encara que la relació s'escrigui en una sola direcció (X HIJO DE Y), a efectes de "ser família" la connexió funciona en els dos sentits: si X és família d'Y, Y també ho és de X.
• No et quedis només mirant si hi ha una línia directa amb els dos noms: cal seguir la cadena de connexions (família llunyana).
• Vigila quantes línies de relacions llegeixes en cada cas (compte amb el desfàs entre M i M-1).

Pista per a Python

from collections import defaultdict, deque

casos = int(input())
for _ in range(casos):
    m = int(input())
    graf = defaultdict(set)
    for _ in range(m - 1):
        parts = input().split()
        x, y = parts[0], parts[-1]   # "X HIJO DE Y"
        graf[x].add(y)
        graf[y].add(x)

    consulta = input().strip()

    # BFS des de THOR per trobar tots els familiars connectats
    visitats = {"THOR"}
    cua = deque(["THOR"])
    while cua:
        actual = cua.popleft()
        for vei in graf[actual]:
            if vei not in visitats:
                visitats.add(vei)
                cua.append(vei)

    print("SI" if consulta in visitats else "NO")

El graf es crea de nou (graf = defaultdict(set)) a cada cas, dins del bucle principal.