Este es un problema dinámico: en cualquier momento, una persona mayor puede unirse a un nodo de gestión o ser transferida de un nodo a otro.

Formato de entrada

La primera línea contiane dos números enteros positivos: N (≤104) que representa el número total de personas mayores, identificadas del 1 al N; y M (≤105) que indica el número total de relaciones de pertenencia.

A continuación, hay M líneas, cada una con una relación de pertenencia en el formato:

A B

Donde A pertenece a B. Si A o B es un nodo de gestión, se representa con hasta 4 letras mayúsculas; si es una persona mayor, se usa su número de identificación. Se garantiza que cada A tiene un único superior B, y que solo el sistema central no tiene superior. Además, ninguna persona mayor actúa como nodo de gestión, es decir, B siempre es un nodo de gestión y nunca un número de persona mayor. Sin embargo, un nodo de gestión puede supervisar tanto nodos subordinados como atender directamente a un grupo de personas mayores.

Luego, cada línea contiene una instrucción en el formato:

Instrucción Contenido

Si la Instrucción es T, indica el ingreso o traslado de una persona mayor. El Contenido incluye el número de la persona mayor y el nombre del nodo de gestión destino, separados por un espacio. Si la instrucción es Q, el Contenido es el nombre de un nodo de gestión, y se debe mostrar la cantidad de personas mayores bajo su cuidado. Si la instrucción es E, indica el fin de la entrada. Se garantiza que el número total de instrucciones no excederá de 100.

Formato de salida

Para cada instrucción T, se actualiza la asignación de la persona mayor al nodo de gestión correspondiente. Para cada instrucción Q, se imprime en una línea la cantidad de personas mayores a cargo del nodo de gestión especificado. El programa termina al leer la instrucción E.

Ejemplo de entrada

10 23
EAST CNTR
ZJ EAST
SD EAST
WEST CNTR
SX WEST
HZ ZJ
JN SD
2 JN
8 JTH
6 XAHP
4 ZDYH
5 ZDYH
ZDYH HZ
HUZ ZJ
JX ZJ
1 JX
3 JN
WZ ZJ
XAHP XIAN
XIAN SX
YL SX
JTH XIAN
7 XAHP
Q EAST
T 1 YL
Q EAST
Q SX
T 8 ZDYH
Q HZ
Q HUZ
T 10 XAHP
Q CNTR
E

Ejemplo de salida

5
4
4
3
0
9

Enfoque de solución

Se puede modelar la jerarquía como una estructura enlazada, donde cada nodo tiene un padre. Dado que los identificadores de personas mayores son numéricos y los de los nodos de gestión son alfanuméricos, no hay conflicto al manejarlos en una misma estructura. Una solución eficiente utiliza un mapa desordenado (unordered_map) para registrar las relaciones padre-hijo y para llevar la cuenta de las personas mayores asignadas a cada nodo. Al insertar una nueva relación o realizar un traslado, se actualizen todos los ancestros en la cadena.

Implementación propuesta

El siguiente código en C++ resuelve el problema. Se han reestructurado las variables y la lógica para mayor claridad, manteniendo la funcionalidad original.

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

void actualizarCadena(unordered_map<string, string>& padre, unordered_map<string, int>& conteo, const string& nodo, int cambio) {
    string actual = nodo;
    while (!actual.empty()) {
        conteo[actual] += cambio;
        actual = padre[actual];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int totalPersonas, totalRelaciones;
    cin >> totalPersonas >> totalRelaciones;

    unordered_map<string, string> nodoPadre;
    unordered_map<string, int> personasACargo;

    for (int i = 0; i < totalRelaciones; ++i) {
        string hijo, padre;
        cin >> hijo >> padre;
        nodoPadre[hijo] = padre;
        int incremento = 1;  // Por defecto, si es una persona mayor.
        if (!isdigit(hijo[0])) {
            incremento = personasACargo[hijo];  // Si es un nodo de gestión, usa su conteo actual.
        }
        actualizarCadena(nodoPadre, personasACargo, padre, incremento);
    }

    string instruccion;
    while (cin >> instruccion && instruccion != "E") {
        if (instruccion == "Q") {
            string nodoConsulta;
            cin >> nodoConsulta;
            cout << personasACargo[nodoConsulta] << "\n";
        } else if (instruccion == "T") {
            string persona, destino;
            cin >> persona >> destino;
            // Eliminar la persona de su cadena actual.
            string actual = nodoPadre[persona];
            while (!actual.empty()) {
                personasACargo[actual]--;
                actual = nodoPadre[actual];
            }
            // Reasignar la persona al nuevo nodo.
            nodoPadre[persona] = destino;
            // Agregar la persona a la nueva cadena.
            actual = destino;
            while (!actual.empty()) {
                personasACargo[actual]++;
                actual = nodoPadre[actual];
            }
        }
    }

    return 0;
}