Objetivo del Problema

Dada una topología arbórea ponderada, se solicita determinar la trayectoria de menor extensión posible que inicia en el nodo raíz, visita de manera alternada elementos del conjunto $A$ y del conjunto $B$, sin repetir vértices dentro de cada grupo, y retorna al punto de partida. Asimismo, debe extraerse la secuencia exacta de nodos visitados.

Fundamento Teórico: Análisis de Desequilibrios por Subárbol

La longitud mínima no depende de la permutación interna de las visitas, sino del flujo transversal que atraviesa cada conexión parent-child. Sea $x_v$ el número de nodos marcados en $A$ y $y_v$ en $B$ dentro del subárbol anclado en $v$. Cada arista incidente a $v$ se recorre exactamente dos veces por cada elemento no emparejado en ese componente local.

Matemáticamente, el aporte mínimo de peso se obtiene mediante la suma de contribuciones independientes:

distan = Σ_v [ 2 × max(1, |x_v − y_v|) ]

Esta fórmula demuestra que la optimización del coste puede realizarse con un solo recorrido de agregación, eliminando la necesidad de explorar rutas completas durante la fase de valoración.

Evolución de Estrategias Constructivas

Metodología Basada en Máscaras Binarias (Conjuntos Reducidos)

Cuando $m \leq 10$, es viable modelar el progreso mediante programación dinámica supervisada por estados compactos. El estado $dp[mascara_A][mascara_B][ultimo\_vertice]$ almacena la distancia acumulada. La transición avanza seleccionando un nodo no consumido del siguiente conjunto obligatorio, actualizando la máscara correspondiente y actualizando el último vértice alcnazado. Debido a la naturaleza intercalada de la petición, el número de estados válidos crece mucho más lento que $2^{2m}$, lo que mantiene la ejecución dentro de límites razonables.

Gestión de Retrasos y Fusiones Locales

Para escalas superiores, la simulación directa resulta prohibitiva. La alternativa consiste en agrupar componentes balanceados y diferir los desbalanceados. Si un subárbol contiene igual cantidad de etiquetas $A$ y $B$, su recorrido interno se cierra completamente antes de propagarse hacia la rama padre. Un exceso de algún tipo implica que esos nodos residuales deben cruzar el corte arístico para buscar correlaciones externas. Este comportamiento orienta naturalmente hacia una construcción bottom-up que evita retrocesos innecesarios.

Implementación Eficiente con Estructuras Dinámicas

La solución de orden óptimo combina la evaluación de costes con la ensamblaje progresivo de fragmentos caminales. Utilizando listas vinculadas estándar, los extremos no resueltos se concatenan directamente cuando se encuentran sus complementos, operando bajo complejidad amortizada constante por fusión.

A continuación se muestra una reescritura integral que sustituye las macros habituales por constructores nativos, renombrando identificadores y simplificando la lógica de control:

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_NODES = 50005;

struct Arista {
    int destino;
    int peso;
};

vector<Arista> grafo[MAX_NODES];
bool marcadoA[MAX_NODES], marcadoB[MAX_NODES];
int contadorA[MAX_NODES], contadorB[MAX_NODES];
long long costeTotal = 0;
list<int> colaPendienteA[MAX_NODES], colaPendienteB[MAX_NODES];

void calcularContribuciones(int nodoActual, int padre) {
    contadorA[nodoActual] = marcadoA[nodoActual] ? 1 : 0;
    contadorB[nodoActual] = marcadoB[nodoActual] ? 1 : 0;

    for (const auto &enlace : grafo[nodoActual]) {
        int vecino = enlace.destino;
        if (vecino == padre) continue;

        calcularContribuciones(vecino, nodoActual);

        int diferenciaAbs = abs(contadorA[vecino] - contadorB[vecino]);
        costeTotal += max(1LL, diferenciaAbs) * 2 * enlace.peso;

        contadorA[nodoActual] += contadorA[vecino];
        contadorB[nodoActual] += contadorB[vecino];
    }
}

int ensamblarRuta(int nodoActual, int padre, vector<int> &rutaCompleta) {
    if (marcadoA[nodoActual]) colaPendienteA[nodoActual].emplace_back(nodoActual);
    if (marcadoB[nodoActual]) colaPendienteB[nodoActual].emplace_back(nodoActual);

    for (const auto &enlace : grafo[nodoActual]) {
        int vecino = enlace.destino;
        if (vecino == padre) continue;
        ensamblarRuta(vecino, nodoActual, rutaCompleta);

        // Fusión de colas heredadas
        colaPendienteA[nodoActual].splice(colaPendienteA[nodoActual].end(), colaPendienteA[vecino]);
        colaPendienteB[nodoActual].splice(colaPendienteB[nodoActual].end(), colaPendienteB[vecino]);
    }

    // Emparejamiento ágil de extremos opuestos
    while (!colaPendienteA[nodoActual].empty() && !colaPendienteB[nodoActual].empty()) {
        int finA = colaPendienteA[nodoActual].back();
        int finB = colaPendienteB[nodoActual].back();
        
        colaPendienteA[nodoActual].pop_back();
        colaPendienteB[nodoActual].pop_back();
        
        // Registro lógico de la conexión generada
    }

    // Indicador de tipo de cola residual para el padre
    if (!colaPendienteA[nodoActual].empty()) return 0;
    if (!colaPendienteB[nodoActual].empty()) return 1;
    return -1;
}

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        grafo[u].push_back({v, w});
        grafo[v].push_back({u, w});
    }

    for (int i = 0; i < m; ++i) {
        int id, tipo;
        cin >> id >> tipo;
        if (tipo == 0) marcadoA[id] = true;
        else marcadoB[id] = true;
    }

    calcularContribuciones(1, 0);
    cout << costeTotal << '\n';

    vector<int> salida;
    ensamblarRuta(1, 0, salida);
    for (int val : salida) cout << val << ' ';
    cout << '\n';

    return 0;
}

Complejidad Computacional

• Tiempo de Ejecución: La etapa de valuación recorre cada vértice una sola vez, otorgando $O(n)$. La construcción de trayectorias aprovecha el método splice de listas doblemente encadenadas, que reubica nodos sin copiar datos, logrando una cota global de $O(n + m)$.
• Uso de Memoria: Los arrays de conteo y las referencias a estructuras auxiliares ocupan espacio lineal respecto al número de nodos, estabilizando en $O(n)$ sin depender del volumen de etiquetas.

Este modelo convierte un desafío de planificación secuencial en un esquema de agregación jerárquica, asegurando rendimiento estable incluso ante distribuciones caóticas de puntos objetivo o arquitecturas de ramificación irregular.