Este artigo explora soluções para diversos problemas algorítmicos, abordando desde manipulações básicas de arrays até estruturas de dados avançadas e algoritmos de grafos. Cada seção apresenta o problema, uma análise da estratégia de solução e uma implementação em C++.

Problema A: Transformação de Array

Dado um array de comprimento \(n\), podemos selecionar dois elementos adjacentes \(a_i\) e \(a_{i+1}\) e substituí-los por um único número \(x\), onde \(\operatorname{min}(a_i, a_{i+1}) \le x \le \operatorname{max}(a_i, a_{i+1})\). A questão é determinar se, após várias operações, o array pode ser reduzido a um único elemento com o valor \(k\).

A propriedade crucial a observar é que, a cada operação, o novo elemento \(x\) está sempre contido no intervalo fechado definido pelos dois elementos adjacentes. Isso implica que o valor mínimo global do array nunca pode diminuir e o valor máximo global nunca pode aumentar. Consequentemente, o intervalo \( [\operatorname{min}(a), \operatorname{max}(a)] \), que contém todos os elementos, é um invariante do processo. Para que o array seja reduzido a um único valor \(k\), é necessário e suficiente que \(k\) esteja dentro do intervalo \( [\operatorname{min}(a_{\text{inicial}}), \operatorname{max}(a_{\text{inicial}})] \). Podemos sempre escolher \(x\) para ser o mínimo ou o máximo atual, permitindo-nos consolidar elementos até que apenas o mínimo e o máximo originais permaneçam, ou até que atinjamos o valor \(k\) se ele estiver nesse intervalo.

#include <iostream>
#include <vector>
#include <algorithm> // Para std::min e std::max

void resolver_caso() {
    int tamanho_array;
    std::cin >> tamanho_array;

    long long valor_minimo = 2e18; // Inicializa com um valor grande
    long long valor_maximo = -2e18; // Inicializa com um valor pequeno

    for (int i = 0; i < tamanho_array; ++i) {
        long long elemento;
        std::cin >> elemento;
        valor_minimo = std::min(valor_minimo, elemento);
        valor_maximo = std::max(valor_maximo, elemento);
    }

    long long valor_alvo_k;
    std::cin >> valor_alvo_k;

    if (valor_minimo <= valor_alvo_k && valor_alvo_k <= valor_maximo) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

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

    int num_testes;
    std::cin >> num_testes;
    while (num_testes--) {
        resolver_caso();
    }
    return 0;
}

Problema B: Par com Módulo Par

Dada uma sequência estritamente crescente \(a_1 < a_2 < \cdots < a_n\), precisamos encontrar um par de índices \(i, j\) tal que \(a_i < a_j\) e \(a_j \pmod{a_i}\) seja um número par. O número de elementos \(n\) pode ser de até \(10^5\).

Vamos analisar os casos de paridade:

1. Existem pelo menos dois números pares: Se houver \(a_x\) e \(a_y\) ambos pares, podemos escolher o par \((\min(a_x, a_y), \max(a_x, a_y))\). O módulo de um número par por outro número par sempre resulta em um número par. Por exemplo, \(4 \pmod 2 = 0\) (par).
2. Existe exatamente um número par: Seja \(a_e\) o único número par. Podemos tentar emparelhá-lo com qualquer número ímpar \(a_o\). Se \(a_e \pmod{a_o}\) for par, encontramos uma solução. Ou se \(a_o \pmod{a_e}\) for par. Por exemplo, \(3 \pmod 2 = 1\) (ímpar), mas \(6 \pmod 3 = 0\) (par). A chave é que a diferença entre dois números com a mesma paridade é par, e a diferença entre números com praidades diferentes é ímpar. \(a_j \pmod{a_i} = a_j - k \cdot a_i\) para algum inteiro \(k\). Para que o resultado seja par, \(a_j\) e \(k \cdot a_i\) devem ter a mesma paridade.
3. Todos os números são ímpares: Neste caso, \(a_i\) e \(a_j\) são ambos ímpares. Para que \(a_j \pmod{a_i}\) seja par, precisamos que \(a_j - k \cdot a_i\) seja par. Como \(a_j\) é ímpar, \(k \cdot a_i\) também deve ser ímpar. Como \(a_i\) é ímpar, isso significa que \(k\) deve ser ímpar. Se encontrarmos um par \(a_i, a_j\) tal que \(a_i < a_j < 2 \cdot a_i\), então \(k=1\). Como \(k=1\) é ímpar, \(a_j \pmod{a_i} = a_j - a_i\) será par (diferença de dois ímpares). Se tal par não existe, isso significa que os números crescem rapidamente (exponencialmente), como em \(a_2 \ge 2a_1, a_3 \ge 2a_2, \ldots\). Isso limita o número de elementos ímpares que precisam ser verificados por força bruta, pois a sequência teria no máximo \(\log V\) elementos, onde \(V\) é o valor máximo. Portanto, uma busca por força bruta em todos os pares \((a_i, a_j)\) para os números ímpares seria no máximo \(O(N \log V)\), o que é eficiente o suficiente.

#include <iostream>
#include <vector>
#include <algorithm> // Para std::min, std::max, std::sort

void resolver_caso() {
    int num_elementos;
    std::cin >> num_elementos;

    std::vector<long long> elementos_pares;
    std::vector<long long> elementos_impares;

    for (int i = 0; i < num_elementos; ++i) {
        long long val;
        std::cin >> val;
        if (val % 2 == 0) {
            elementos_pares.push_back(val);
        } else {
            elementos_impares.push_back(val);
        }
    }

    if (elementos_pares.size() >= 2) {
        // Caso 1: Dois ou mais números pares. Qualquer par funciona.
        // Pegamos os dois primeiros para simplicidade.
        std::cout << std::min(elementos_pares[0], elementos_pares[1]) << " "
                  << std::max(elementos_pares[0], elementos_pares[1]) << "\n";
        return;
    }

    if (elementos_pares.size() == 1) {
        // Caso 2: Exatamente um número par.
        // Tentamos emparelhá-lo com cada ímpar.
        long long unico_par = elementos_pares[0];
        for (long long impar_val : elementos_impares) {
            long long maior = std::max(impar_val, unico_par);
            long long menor = std::min(impar_val, unico_par);
            if ((maior % menor) % 2 == 0) {
                std::cout << menor << " " << maior << "\n";
                return;
            }
        }
    }

    // Caso 3: Todos os números são ímpares (ou nenhum par e nenhum ímpar,
    // mas o problema garante uma solução se n >= 2, o que implicaria pelo menos 2 ímpares).
    std::sort(elementos_impares.begin(), elementos_impares.end());

    for (size_t i = 0; i < elementos_impares.size(); ++i) {
        for (size_t j = i + 1; j < elementos_impares.size(); ++j) {
            if ((elementos_impares[j] % elementos_impares[i]) % 2 == 0) {
                std::cout << elementos_impares[i] << " " << elementos_impares[j] << "\n";
                return;
            }
        }
    }

    // Se nenhuma solução foi encontrada (o problema afirma que sempre há uma solução,
    // então este trecho não deve ser alcançado se n >= 2).
    std::cout << "-1\n";
}

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

    int num_testes;
    std::cin >> num_testes;
    while (num_testes--) {
        resolver_caso();
    }
    return 0;
}

Problema C: Calabouço e Espadas

Você está em um calabouço enfrentando \(m\) monstros e possui \(n\) espadas. Cada espada \(i\) tem um dano \(a_i\), e cada monstro \(i\) tem \(b_i\) pontos de vida. Ao usar uma espada de dano \(x\) para matar um monstro \(i\), a espada é consumida. Se \(c_i > 0\), você ganha uma nova espada com dano \(\operatorname{max}(x, c_i)\); caso contrário, não ganha nada. O objetivo é matar o máximo de monstros possível, sendo que cada monstro pode ser morto apenas uma vez. As quantidades \(n, m\) podem ir até \(2 \times 10^5\).

Para maximizar o número de monstros mortos, usamos uma abordagem gulosa. A estratégia é a seguinte:

1. Organização Inicial:
   • Armazene as espadas em uma fila de prioridade mínima (std::priority_queue<int, std::vector<int>, std::greater<int>>) para sempre ter acesso à espada de menor dano disponível.
   • Armazene os monstros como pares \((b_i, c_i)\). Ordene os monstros por pontos de vida \(b_i\) em ordem crescente. Se dois monstros tiverem os mesmos pontos de vida, ordene-os por \(c_i\) em ordem decrescente (recompensa maior primeiro). Isso é importante porque se podemos matar vários monstros com uma espada, queremos escolher aquele que nos dá a melhor recompensa.
2. Processamento:
   • Itere enquanto houver espadas disponíveis.
   • Pegue a espada de menor dano \(x\) da fila de prioridade de espadas.
   • Para essa espada \(x\), identifique todos os monstros que podem ser mortos (aqueles com \(b_i \le x\)) e adicione seus valores de recompensa \(c_i\) a uma fila de prioridade máxima (std::priority_queue<int>). Esta fila armazenará as recompensas dos monstros que podem ser mortos com a espada atual ou espadas mais fortes, mas ainda não foram.
   • Se a fila de prioridade de recompensas não estiver vazia, significa que há monstros que podemos matar. Escolha o monstro com a maior recompensa \(c_{max}\). Mate-o (remova \(c_{max}\) da fila), incremente a contagem de monstros mortos. Se \(c_{max} > 0\), adicione uma nova espada de dano \(\operatorname{max}(x, c_{max})\) de volta à fila de prioridade de espadas. A condição \(c_i > 0\) é importante.

A lógica de sempre adicionar \(\operatorname{max}(x, c_i)\) garante que a nova espada tenha um dano pelo menos tão grande quanto a espada que a gerou. Isso impede que espadas se tornem mais fracas à medida que avançamos, mantendo a capacidade de matar monstros mais fortes. A ordenação dos monstros e o uso das filas de prioridade permitem sempre tomar a melhor decisão gulosa em cada passo.

#include <iostream>
#include <vector>
#include <queue>      // Para std::priority_queue
#include <algorithm>  // Para std::sort, std::max
#include <utility>    // Para std::pair

struct Monstro {
    int hp;
    int recompensa_c;

    // Custom comparator para ordenar monstros:
    // 1. Por HP crescente.
    // 2. Por recompensa_c decrescente (se HP for igual).
    bool operator<(const Monstro& outro) const {
        if (hp != outro.hp) {
            return hp < outro.hp;
        }
        return recompensa_c > outro.recompensa_c; // Recompensa maior primeiro
    }
};

void resolver_caso() {
    int num_espadas, num_monstros;
    std::cin >> num_espadas >> num_monstros;

    // Fila de prioridade mínima para espadas (menor dano primeiro)
    std::priority_queue<int, std::vector<int>, std::greater<int>> espadas_disponiveis;
    for (int i = 0; i < num_espadas; ++i) {
        int dano_espada;
        std::cin >> dano_espada;
        espadas_disponiveis.push(dano_espada);
    }

    std::vector<Monstro> monstros(num_monstros);
    for (int i = 0; i < num_monstros; ++i) {
        std::cin >> monstros[i].hp;
    }
    for (int i = 0; i < num_monstros; ++i) {
        std::cin >> monstros[i].recompensa_c;
    }

    // Ordena monstros por HP e depois por recompensa
    std::sort(monstros.begin(), monstros.end());

    int monstros_mortos_count = 0;
    int indice_monstro_atual = 0; // Ponteiro para o próximo monstro a ser considerado

    // Fila de prioridade máxima para recompensas de monstros que podem ser mortos
    std::priority_queue<int> recompensas_monstros_disponiveis;

    while (!espadas_disponiveis.empty()) {
        int dano_espada_atual = espadas_disponiveis.top();
        espadas_disponiveis.pop();

        // Adiciona monstros que podem ser mortos com a espada atual (ou mais forte)
        while (indice_monstro_atual < num_monstros && monstros[indice_monstro_atual].hp <= dano_espada_atual) {
            recompensas_monstros_disponiveis.push(monstros[indice_monstro_atual].recompensa_c);
            indice_monstro_atual++;
        }

        if (!recompensas_monstros_disponiveis.empty()) {
            int recompensa_escolhida = recompensas_monstros_disponiveis.top();
            recompensas_monstros_disponiveis.pop();

            monstros_mortos_count++;
            if (recompensa_escolhida > 0) {
                espadas_disponiveis.push(std::max(recompensa_escolhida, dano_espada_atual));
            }
        }
    }

    std::cout << monstros_mortos_count << "\n";
}

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

    int num_testes;
    std::cin >> num_testes;
    while (num_testes--) {
        resolver_caso();
    }
    return 0;
}

Problema D: Transformação de Strings

Queremos transformar uma string \(s\) em uma string \(t\), ambas de comprimento \(n\). A única operação permitida é: criar uma nova string \(s'\) onde \(s'_i = s_{i-1}\) para cada \(i > 0\) (assumindo 0-indexação para \(s'_0 = s_0\)), e então substituir \(s\) por \(s'\). A pergunta é qual o número mínimo de operações \(L\) necessárias para transformar \(s\) em \(t\), dado que \(L\) deve ser no máximo \(k\). Se não for possível dentro de \(k\) operações, ou se for impossível, imprima \(-1\). Caso contrário, imprima \(L\) e as strings intermediárias.

A operação \(s'_i = s_{i-1}\) significa que um caractere pode "se mover" uma posição para a direita. Mais precisamente, o caractere na posição \(i\) pode ser substituído pelo caractere que estava na posição \(i-1\) na string anterior. Após \(L\) operações, um caractere originalmente em \(s_p\) pode alcançar a posição \(i\) se \(p \ge i - L\). Além disso, a cada operação, todos os caracteres se movem efetivamente uma posição para a direita, ou permanecem no lugar. Isso implica que um caractere em \(s_p\) não pode ser "ultrapassado" por um caractere \(s_{p'}\) onde \(p' > p\) se ambos se movem para a direita. Em outras palavras, se \(t_i\) vem de \(s_{p_i}\) e \(t_{i-1}\) vem de \(s_{p_{i-1}}\), então devemos ter \(p_{i-1} \le p_i\).

O problema pode ser resolvido com uma busca binária no número mínimo de operações \(L\) (de \(0\) a \(k\)). Para um dado \(L\):

1. Função de Verificação (is_transformable_in_l_steps(L)):
   • Para cada posição \(i\) de \(t\) (de \(0\) a \(n-1\)), queremos encontrar a posição mais à esquerda \(p_i\) na string original \(s\) tal que \(s_{p_i} = t_i\).
   • Este \(p_i\) deve satisfazer duas condições:
     • \(p_i \ge i - L\) (o caractere original deve ter tido tempo de se mover até a posição \(i\)).
     • \(p_i \ge p_{i-1}\) (os caracteres não podem se cruzar; a ordem relativa dos caracteres originais é preservada).
   • Percorra \(i\) de \(0\) a \(n-1\), mantendo um prev_p = 0. Para cada \(i\), procure o menor \(p_i\) em \( [ \max(prev\_p, i - L), i ] \) tal que \(s_{p_i} = t_i\). Se encontrar, atualize prev_p = p_i. Se não encontrar para algum \(i\), então \(L\) não é suficiente.
2. Reconstrução das Etapas:
   • Depois de encontrar o menor \(L\) que satisfaz a condição, precisamos reconstruir as strings intermediárias.
   • Primeiro, determine o array \(p\) (onde \(t_i\) vem de \(s_{p_i}\)) usando a lógica da função de verificação. Calcule o "deslocamento" necessário para cada caractere como \(shift_i = i - p_i\).
   • Então, simule \(L\) operações. Em cada passo, crie uma nova string. Para cada posição \(j\), se o caractere em \(t_j\) ainda precisa se mover (ou seja, \(shift_j > 0\)), então o novo \(s'_j\) será o \(s_{j-1}\) da string atual. Decremente \(shift_j\).

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Para std::max, std::min

const int MAXN_LEN = 1e6 + 10;
int n_len, k_max_ops;
int original_pos_shift[MAXN_LEN]; // Armazena i - p_i
std::string s_source, t_target;

// Verifica se a transformação é possível em 'current_L_ops' operações
bool is_transformable_in_l_steps(int current_L_ops) {
    int last_source_pos = -1; // Última posição de s usada
    for (int i = 0; i < n_len; ++i) { // Para cada caractere em t_target
        int min_possible_source_pos = std::max(last_source_pos, i - current_L_ops);
        int max_possible_source_pos = i;
        bool found = false;
        for (int p_idx = min_possible_source_pos; p_idx <= max_possible_source_pos; ++p_idx) {
            if (p_idx >= 0 && s_source[p_idx] == t_target[i]) {
                found = true;
                last_source_pos = p_idx;
                break;
            }
        }
        if (!found) {
            return false;
        }
    }
    return true;
}

void resolver_caso() {
    std::cin >> n_len >> k_max_ops >> s_source >> t_target;

    if (s_source == t_target) {
        std::cout << "0\n";
        return;
    }

    int low = 0, high = k_max_ops, min_L = -1;
    // Busca binária para encontrar o menor L
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (is_transformable_in_l_steps(mid)) {
            min_L = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    if (min_L == -1) { // Não foi possível encontrar um L válido
        std::cout << "-1\n";
        return;
    }

    // Reconstruir o array de deslocamentos para o min_L
    int last_source_pos = -1;
    for (int i = 0; i < n_len; ++i) {
        int min_possible_source_pos = std::max(last_source_pos, i - min_L);
        int max_possible_source_pos = i;
        for (int p_idx = min_possible_source_pos; p_idx <= max_possible_source_pos; ++p_idx) {
            if (p_idx >= 0 && s_source[p_idx] == t_target[i]) {
                last_source_pos = p_idx;
                original_pos_shift[i] = i - p_idx; // Quantas posições o char s[p_idx] deve se mover
                break;
            }
        }
    }

    std::cout << min_L << "\n";
    std::string current_str_state = s_source;
    std::string next_str_state;

    for (int step = 0; step < min_L; ++step) {
        next_str_state = current_str_state; // Começa com a string do passo anterior
        for (int i = 0; i < n_len; ++i) {
            if (original_pos_shift[i] > 0) { // Se este caractere em t[i] ainda precisa se mover para chegar
                if (i > 0) { // Não podemos mover s[0] para a posição -1
                    next_str_state[i] = current_str_state[i - 1];
                }
                original_pos_shift[i]--; // Uma operação realizada
            }
        }
        std::cout << next_str_state << "\n";
        current_str_state = next_str_state; // Atualiza a string atual para o próximo passo
    }
}

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

    int num_testes;
    std::cin >> num_testes;
    while (num_testes--) {
        resolver_caso();
    }
    return 0;
}

Problema E: Marcação de Arestas em Grafo e Custo Mínimo

Dada um grafo não direcionado e conectado com \(n\) vértices e \(m\) arestas \((u, v, w)\) (onde \(w\) é o peso da aresta e as arestas são indexadas por sua ordem de entrada de \(0\) a \(m-1\)). Começando no vértice \(1\), você deve marcar cada aresta pelo menos uma vez e retornar ao vértice \(1\). Existem duas operações de movimento:

1. Marcar a aresta \((x,y)\) e mover-se para \(y\), com custo igual ao peso da aresta.
2. Escolher um caminho de \(x\) para \(z\) (não necessariamente simples) e mover-se para \(z\), com custo igual ao peso da aresta de maior índice no caminho.

O objetivo é calcular o custo total mínimo.

O custo total inicial incluirá a soma de todos os pesos de aresta, pois cada aresta deve ser marcada pelo menos uma vez. Se o grafo tiver um Circuito Euleriano (ou seja, todos os vértices têm grau par), então um único percurso do Circuito Euleriano marcará todas as arestas e o custo será exatamente a soma dos pesos. No entanto, se existirem vértices com grau ímpar, o grafo não possui um Circuito Euleriano. Para resolver isso, precisamos adicionar "arestas virtuais" ao grafo para torná-lo Euleriano. Uma aresta virtual entre dois vértices \(u\) e \(v\) significa que nos movemos de \(u\) para \(v\) usando a segunda operação, sem marcar as arestas do caminho real. O custo dessa aresta virtual é o custo mínimo possível da segunda operação: o peso máximo de uma aresta em um caminho de \(u\) para \(v\).

O problema se reduz a encontrar um emparelhamento de custo mínimo para todos os vértices de grau ímpar, onde o custo de uma "aresta virtual" entre \(u\) e \(v\) é o peso mínimo do gargalo (aresta de maior peso) em qualquer caminho entre \(u\) e \(v\). Este valor pode ser encontrado usando uma abordagem similar a uma Árvore Geradora Mínima (MST), ou mais especificamente, uma "reconstruction tree" baseada em Union-Find.

1. Estrutura de Dados Union-Find (DSU): Usaremos uma DSU para gerenciar componentes conectados. Cada nó na DSU representa um componente.
   • parent_arr[i]: o pai do conjunto ao qual i pertence.
   • min_path_weight[i]: o peso mínimo de gargalo de uma aresta que conectou i ou um de seus descendentes ao componente do seu pai no processo de construção.
   • is_odd_degree_in_comp[i]: um booleano que indica se o número de vértices de grau ímpar no componente i é ímpar (XOR de graus).
   • comp_parent_arr[i]: um ponteiro para o pai de i na árvore de reconstrução que está sendo formada.
   • is_pair_closed[k]: booleano, indica se o componente k recém-formado fechou um par de nós de grau ímpar.
2. Processamento de Arestas: Processamos as arestas na ordem de seus índices de entrada (que já estão implícitos ao iterar a lista de arestas). Para cada aresta \((u, v, w)\):
   • Adicione \(w\) ao custo total inicial.
   • Atualize a paridade do grau de \(u\) e \(v\) (is_odd_degree_in_comp[u] ^= 1, etc.).
   • Encontre os líderes dos componentes de \(u\) e \(v\), digamos \(root_u\) e \(root_v\).
   • Se \(root_u == root_v\), esta aresta fecha um ciclo. Atualize min_path_weight[root_u] = min(min_path_weight[root_u], w).
   • Se \(root_u \ne root_v\), mescle os componentes. Crie um novo nó \(k\) para representar o componente mesclado.
     • O pai do novo nó \(k\) na estrutura Union-Find será ele mesmo.
     • comp_parent_arr[root_u] = k e comp_parent_arr[root_v] = k.
     • min_path_weight[k] = w.
     • is_odd_degree_in_comp[k] = is_odd_degree_in_comp[root_u] ^ is_odd_degree_in_comp[root_v].
     • is_pair_closed[k] = is_odd_degree_in_comp[root_u] && is_odd_degree_in_comp[root_v] (significa que se ambos tinham grau ímpar local, eles foram emparelhados por esta aresta).
3. Pós-Processamento: Percorra os nós do DSU em ordem decrescente (do mais novo para o mais antigo, i.e., de \(2N-1\) a \(1\)).
   • Propague os valores de min_path_weight para cima: min_path_weight[i] = min(min_path_weight[i], min_path_weight[comp_parent_arr[i]]).
   • Se is_pair_closed[i] for verdadeiro, significa que um par de nós de grau ímpar foi emparelhado por um caminho cujo gargalo mínimo é min_path_weight[i]. Adicione min_path_weight[i] ao custo total.

O custo total final será a soma dos pesos de todas as arestas originais mais a soma dos pesos de gargalo mínimos das arestas virtuais necessárias para emparelhar os vértices de grau ímpar.

#include <iostream>
#include <vector>
#include <numeric>  // Para std::iota
#include <algorithm> // Para std::min
#include <array>    // Para std::array

const int MAX_NODES = 2e6 + 5; // Max 2*N para Union-Find nodes
int num_nodes_e, num_edges_e;

// DSU structures
int parent_arr[MAX_NODES]; // Parent in DSU
int min_bottleneck_weight[MAX_NODES]; // Min bottleneck weight for path in component
int component_parent_in_tree[MAX_NODES]; // Parent in the reconstruction tree
bool is_node_odd_degree[MAX_NODES]; // Tracks if component's "external" degree parity is odd
bool is_odd_pair_resolved[MAX_NODES]; // True if this component resolved an odd-degree pair

// Edge structure: {u, v, w}
std::vector<std::array<int, 3>> edges_list;

// Find operation with path compression
int find_set(int i) {
    if (i == parent_arr[i])
        return i;
    return parent_arr[i] = find_set(parent_arr[i]);
}

void resolver_caso_e() {
    std::cin >> num_nodes_e >> num_edges_e;
    long long total_min_cost = 0;

    // Initialize DSU for N nodes and potential 2N-1 new nodes for merging components
    for (int i = 1; i <= 2 * num_nodes_e; ++i) {
        parent_arr[i] = i;
        component_parent_in_tree[i] = 0; // No tree parent initially
        is_node_odd_degree[i] = false; // All degrees even initially
        is_odd_pair_resolved[i] = false; // No pairs resolved
        min_bottleneck_weight[i] = 2e9 + 7; // Represents infinity
    }

    edges_list.resize(num_edges_e);
    for (auto& edge : edges_list) {
        std::cin >> edge[0] >> edge[1] >> edge[2]; // u, v, w
        total_min_cost += edge[2]; // Sum all edge weights
    }

    int current_new_node_id = num_nodes_e; // Start assigning new IDs after N original nodes

    // Process edges in their input order
    for (const auto& edge : edges_list) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        int root_u = find_set(u);
        int root_v = find_set(v);

        // Update degree parity for original nodes
        // This is done on actual node IDs, not component roots.
        // is_node_odd_degree[u] ^= 1;
        // is_node_odd_degree[v] ^= 1;

        if (root_u == root_v) {
            // Edge forms a cycle within an existing component
            min_bottleneck_weight[root_u] = std::min(min_bottleneck_weight[root_u], weight);
        } else {
            // Merge two components: create a new component node
            current_new_node_id++;
            
            // The new component inherits "odd-ness" from merged components
            // is_node_odd_degree[current_new_node_id] = is_node_odd_degree[root_u] ^ is_node_odd_degree[root_v];
            
            // We flip the parity of the component roots, not the original nodes.
            // This 'is_node_odd_degree' array is for component roots.
            is_node_odd_degree[root_u] ^= 1; // Mark u's root as having an odd connection
            is_node_odd_degree[root_v] ^= 1; // Mark v's root as having an odd connection

            // The new node 'current_new_node_id' represents the merged component.
            // Its 'odd-ness' is the XOR of its children's 'odd-ness'.
            is_node_odd_degree[current_new_node_id] = is_node_odd_degree[root_u] ^ is_node_odd_degree[root_v];

            // If both children had odd 'external' degrees, this merger resolves a pair
            if (is_node_odd_degree[root_u] && is_node_odd_degree[root_v]) {
                is_odd_pair_resolved[current_new_node_id] = true;
            }

            parent_arr[root_u] = current_new_node_id;
            parent_arr[root_v] = current_new_node_id;
            component_parent_in_tree[root_u] = component_parent_in_tree[root_v] = current_new_node_id;
            min_bottleneck_weight[current_new_node_id] = weight;
        }
    }

    // Propagate min_bottleneck_weight upwards and add resolved pair costs
    // Iterate from newest components down to original nodes
    for (int i = 2 * num_nodes_e - 1; i >= 1; --i) {
        if (component_parent_in_tree[i] != 0) { // If it has a parent in the reconstruction tree
            min_bottleneck_weight[i] = std::min(min_bottleneck_weight[i], min_bottleneck_weight[component_parent_in_tree[i]]);
        }
        if (is_odd_pair_resolved[i]) {
            total_min_cost += min_bottleneck_weight[i];
        }
    }
    std::cout << total_min_cost << '\n';
}

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

    int num_test_cases;
    std::cin >> num_test_cases;
    while (num_test_cases--) {
        resolver_caso_e();
    }
    return 0;
}

Problema F1 & F2: Permutações em Árvores e Condições de Ancestralidade

Dada uma árvore \(T\) com \(n\) vértices e raiz em \(1\), e uma sequência \(a\) de comprimento \(n\). O objetivo é contar o número de permutações \(p\) de \( [1, 2, \ldots, n] \) que satisfazem a seguinte condição para todo \(1 \le u \le n\): existem exatamente \(a_u\) vértices \(v\) que são ancestrais de \(u\) em \(T\) E \(p_v < p_u\). A resposta deve ser dada modulo \(998244353\). É garantido que pelo menos uma permutação válida existe.

A condição \(p_v < p_u\) para exatamente \(a_u\) ancestrais \(v\) significa que, considerando o conjunto de \(u\) e seus ancestrais, \(u\) ocupa a \((a_u + 1)\)-ésima menor posição na permutação entre eles. Este é um problema combinatório complexo que geralmente é abordado com uma combinação de decomposição heavy-light (HLD), uma árvore de segmentos (ou Fenwick tree) e cálculo de coeficientes binomiais (combinações).

A estratégia geral envolve:

1. Pré-cálculos para Combinatória: Fatoriais e inversos fatoriais são necessários para calcular \(C(N, K) = \frac{N!}{K!(N-K)!}\pmod{MOD}\).
2. Decomposição Heavy-Light da Árvore: A HLD é utilizada para dividir a árvore em caminhos "pesados" e "leves". Isso permite processar subárvores de forma eficiente, muitas vezes em tempo logarítmico.
   • dfs: Realiza a primeira DFS para calcular tamanhos de subárvores (subtree_size) e identificar o filho pesado (heavy_child) para cada nó.
3. DFS com Segment Tree (dfs1): A segunda DFS usa a decomposição heavy-light para processar os nós. O coração da solução reside aqui:
   • Para cada nó \(u\), os valores de \(a_u\) precisam ser 1-indexados para representar a posição em um array.
   • Uma Árvore de Segmentos (SegmentTree T) mantém o controle das posições disponíveis para os números na permutação. A operação T.qpos(x) encontra a \(x\)-ésima posição disponível.
   • A função dfs1 processa os filhos leves recursivamente. Depois, itera ao longo do caminho pesado, coletando informações sobre os números de ancestrais e suas posições relativas.
   • node_counts[t] (originalmente cnt[t]): Parece armazenar o número de elementos que precisam ser atribuídos a uma posição relativa t.
   • subtree_data[u] (originalmente vec[u]): Armazena informações coletadas de subárvores, possivelmente pares {rank, count}.
   • A cada passo, calcula as contribuições para o total_ans multiplicando por combinações. A expressão combinations(v, node_counts[t] + v) sugere que \(v\) elementos devem ser escolhidos de um total de \(node\_counts[t] + v\) posições.
   • As operações T.add(p, -1) e T.add(i, 1) modificam a árvore de segmentos para refletir a ocupação e liberação de posições.

Esta abordagem usa a estrutura da árvore para dividir o problema e gerencia as restrições de ordenação relativa usando a árvore de segmentos para contar e atribuir posições de forma combinatória. A complexidade de tempo é geralmente \(O(N \log N)\) devido à HLD e operações da árvore de segmentos.

#include <iostream>
#include <vector>
#include <algorithm> // Para std::reverse
#include <array>     // Para std::array

const int MAX_NODES_F = 5e5 + 5;
const int MODULO_VAL = 998244353;
const int SEG_TREE_BLOCK_SIZE = 1 << 19; // Power of 2 >= MAX_NODES_F

long long power_modulo(long long base, int exp) {
    long long res = 1;
    base %= MODULO_VAL;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MODULO_VAL;
        base = (base * base) % MODULO_VAL;
        exp /= 2;
    }
    return res;
}

long long factorial_arr[MAX_NODES_F];
long long inv_factorial_arr[MAX_NODES_F];
long long total_ans_f;

// nCr calculation
long long combinations(int k, int n) {
    if (k < 0 || k > n) return 0;
    return (((factorial_arr[n] * inv_factorial_arr[k]) % MODULO_VAL) * inv_factorial_arr[n - k]) % MODULO_VAL;
}

int required_ancestor_rank[MAX_NODES_F];
int node_counts_f[MAX_NODES_F]; // For segment tree value tracking
int subtree_size_f[MAX_NODES_F];
int heavy_child_f[MAX_NODES_F];
std::vector<int> children_nodes_f[MAX_NODES_F];
std::vector<int> updates_vec_f, positions_vec_f;
std::vector<std::array<int, 2>> subtree_data_f[MAX_NODES_F]; // {rank_in_permutation, count}

// Segment Tree Structure
struct SegmentTree {
    int segment_length[SEG_TREE_BLOCK_SIZE * 2 + 10];

    void initialize() {
        for (int i = 0; i < SEG_TREE_BLOCK_SIZE; ++i) segment_length[i + SEG_TREE_BLOCK_SIZE] = 1;
        for (int i = SEG_TREE_BLOCK_SIZE - 1; i >= 1; --i) segment_length[i] = segment_length[i << 1] + segment_length[i << 1 | 1];
    }

    // Query for the x-th available position (0-indexed)
    int query_position_by_rank(int x) {
        int u = 1;
        while (u < SEG_TREE_BLOCK_SIZE) {
            if (segment_length[u << 1] >= x) u = u << 1;
            else x -= segment_length[u << 1], u = u << 1 | 1;
        }
        return u - SEG_TREE_BLOCK_SIZE;
    }

    // Get the rank of a specific position (0-indexed)
    int get_rank_of_position(int x) {
        int rank_sum = 1; // 1-indexed rank
        x += SEG_TREE_BLOCK_SIZE;
        while (x > 1) {
            if (x & 1) rank_sum += segment_length[x ^ 1]; // If right child, add left sibling's count
            x >>= 1;
        }
        return rank_sum;
    }

    // Add/remove a position to/from the segment tree
    void update_position(int x, int val) {
        x += SEG_TREE_BLOCK_SIZE;
        segment_length[x] += val;
        while (x > 1) x >>= 1, segment_length[x] += val;
    }
} seg_tree;

// DFS to calculate subtree sizes and heavy children
void dfs_compute_sizes(int u) {
    subtree_size_f[u] = 1;
    heavy_child_f[u] = 0;
    for (int v : children_nodes_f[u]) {
        dfs_compute_sizes(v);
        subtree_size_f[u] += subtree_size_f[v];
        if (subtree_size_f[v] > subtree_size_f[heavy_child_f[u]]) heavy_child_f[u] = v;
    }
}

// Main DFS for heavy-light decomposition and permutation count
void dfs_calculate_permutations(int u) {
    std::vector<int> path_nodes;
    for (int v = u; v; v = heavy_child_f[v]) {
        path_nodes.push_back(v);
        for (int k : children_nodes_f[v]) {
            if (k != heavy_child_f[v]) dfs_calculate_permutations(k); // Process light children
        }
    }
    std::reverse(path_nodes.begin(), path_nodes.end());

    updates_vec_f.clear();
    positions_vec_f.clear();

    for (int v : path_nodes) {
        for (int k : children_nodes_f[v]) {
            if (k != heavy_child_f[v]) { // From light children, add their subtree data
                for (auto& item : subtree_data_f[k]) {
                    int pos_idx = seg_tree.query_position_by_rank(item[0]);
                    positions_vec_f.push_back(pos_idx);
                    total_ans_f = (total_ans_f * combinations(item[1], node_counts_f[pos_idx] + item[1])) % MODULO_VAL;
                    node_counts_f[pos_idx] += item[1];
                }
            }
        }
        
        // Find positions for the current node 'v'
        // required_ancestor_rank[v] is 1-indexed (after a[v]++)
        int p_rank = seg_tree.query_position_by_rank(required_ancestor_rank[v]);
        int q_rank = seg_tree.query_position_by_rank(required_ancestor_rank[v] + 1); // Next available rank

        node_counts_f[q_rank] += node_counts_f[p_rank] + 1; // Move elements from p_rank to q_rank, add current node
        node_counts_f[p_rank] = 0;
        
        positions_vec_f.push_back(q_rank);
        updates_vec_f.push_back(p_rank);
        seg_tree.update_position(p_rank, -1); // Mark p_rank as occupied
    }

    // Collect data for parent node
    for (int i : positions_vec_f) {
        if (node_counts_f[i] > 0) {
            subtree_data_f[u].push_back({seg_tree.get_rank_of_position(i), node_counts_f[i]});
            node_counts_f[i] = 0; // Clear for next use
        }
    }

    // Restore segment tree for siblings/parent
    for (int i : updates_vec_f) seg_tree.update_position(i, 1);
    updates_vec_f.clear();
    positions_vec_f.clear();
}

void resolver_caso_f() {
    int n;
    std::cin >> n;

    for (int i = 0; i <= n; ++i) {
        children_nodes_f[i].clear();
        subtree_data_f[i].clear();
        node_counts_f[i] = 0; // Reset counts for segment tree
    }

    for (int i = 2; i <= n; ++i) {
        int f_parent;
        std::cin >> f_parent;
        children_nodes_f[f_parent].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        std::cin >> required_ancestor_rank[i];
        required_ancestor_rank[i]++; // Adjust to 1-indexed rank
    }

    total_ans_f = 1;
    dfs_compute_sizes(1);
    dfs_calculate_permutations(1);

    std::cout << total_ans_f << '\n';
}

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

    factorial_arr[0] = inv_factorial_arr[0] = 1;
    seg_tree.initialize();
    for (int i = 1; i < MAX_NODES_F; ++i) {
        factorial_arr[i] = (factorial_arr[i - 1] * i) % MODULO_VAL;
        inv_factorial_arr[i] = power_modulo(factorial_arr[i], MODULO_VAL - 2);
    }

    int num_test_cases;
    std::cin >> num_test_cases;
    while (num_test_cases--) {
        resolver_caso_f();
    }
    return 0;
}

Problema G: Descoberta Interativa de Árvores Escondidas

Madeline está jogando com uma "máquina sem sentido" que tem uma árvore escondida de tamanho \(n\). Madeline deve descobrir as arestas da árvore fazendo consultas à máquina. Em cada consulta, Madeline fornece uma permutação \(p\) de \( [1, 2, \ldots, n] \). A máquina retorna uma sequência \(q_1, q_2, \ldots, q_n\), onde \(q_i\) é o número de arestas no subgrafo induzido pelo conjunto de vértices \(\{p_1, p_2, \ldots, p_i\}\). A máquina é lenta e Madeline só recebe os resultados de todas as consultas de uma vez. Ela pode fazer no máximo \(31\) consultas. O problema é interativo e não adaptativo (a árvore é fixa).

A chave para este problema é usar as informações das consultas para inferir as propriedades da árvore. O valor \(q_i - q_{i-1}\) (com \(q_0 = 0\)) representa o número de arestas que o vértice \(p_i\) forma com os vértices já introduzidos no subgrafo (ou seja, \(\{p_1, \ldots, p_{i-1}\}\)). Seja \(C(u, P)\) esta contagem para o vértice \(u\) na permutação \(P\).

A estratégia envolve:

1. Calcular os Graus dos Vértices:
   • Faça uma consulta com a permutação \(P_1 = [1, 2, \ldots, n]\) e obtenha \(Q_1\). Para cada \(u = p_i\) em \(P_1\), \(C(u, P_1) = Q_1[i] - Q_1[i-1]\).
   • Faça uma segunda consulta com a permutação \(P_2 = [n, n-1, \ldots, 1]\) (a reversa de \(P_1\)) e obtenha \(Q_2\). Para cada \(u = p_i\) em \(P_2\), \(C(u, P_2) = Q_2[i] - Q_2[i-1]\).
   • O grau total de um vértice \(u\) é \(\operatorname{deg}(u) = C(u, P_1) + C(u, P_2)\). Note que \(P_2\) é a permutação reversa, então para um nó \(u\), \(C(u, P_1)\) conta as arestas de \(u\) para nós com ID menor, e \(C(u, P_2)\) conta as arestas de \(u\) para nós com ID maior. Juntos, eles dão o grau de \(u\).
2. Identificar Vizinhos por Dívidas Ternárias:
   • Para cada posição de dígito ternário \(k\) (de \(0\) até \(\lceil \log_3 n \rceil - 1\)):
     • Particione os vértices em três grupos: \(G_0, G_1, G_2\), baseados no \(k\)-ésimo dígito ternário de \(u-1\) (0, 1 ou 2).
     • Crie três permutações concatenando esses grupos em ordens cíclicas:
       • \(P_{k,0} = (G_0, G_1, G_2)\)
       • \(P_{k,1} = (G_1, G_2, G_0)\)
       • \(P_{k,2} = (G_2, G_0, G_1)\)
     • Para cada uma dessas 3 permutações, faça uma consulta e colete os valores \(C(u, P_{k,j})\) para cada \(u\).
     • A diferença \(C(u, P_{k,j}) - C(u, P_{k,j+1})\) (com \(j+1\) módulo 3) pode ser usada para determinar o número de vizinhos de \(u\) que têm cada um dos dígitos ternários \(0, 1, 2\) na posição \(k\). Seja \(N_u(d, k)\) o número de vizinhos de \(u\) cujo \(k\)-ésimo dígito ternário é \(d\). Podemos resolver um sistema de equações para \(N_u(0, k), N_u(1, k), N_u(2, k)\) usando \(\sum N_u(d,k) = \operatorname{deg}(u)\) e as diferenças obtidas das consultas.
3. Reconstruir a Árvore via Poda de Folhas (Simulação de BFS/Toposort):
   • Inicialize uma fila com todos os vértices que têm grau 1 (folhas).
   • Enquanto a fila não estiver vazia e não tivermos encontrado \(N-1\) arestas:
     • Retire um vértice \(x\) da fila.
     • Se \(\operatorname{deg}(x) \ne 1\), ignore (já foi processado ou não é mais folha).
     • Use os valores \(N_x(d, k)\) (número de vizinhos de \(x\) com dígito \(d\) na posição \(k\)) para determinar a ID do seu único vizinho (o pai \(y\)). A ID de \(y\) pode ser construída bit a bit (ou dígito ternário a dígito ternário). Especificamente, se \(N_x(d, k) = 1\), o \(k\)-ésimo dígito ternário de \(y\) é \(d\).
     • Uma vez que \(y\) é identificado, declare a aresta \((x, y)\) como descoberta.
     • Decremente \(\operatorname{deg}(x)\) e \(\operatorname{deg}(y)\).
     • Atualize os valores \(N_y(d, k)\) para \(y\) (diminua o \(d\)-ésimo contador correspondente a \(x\)).
     • Se \(\operatorname{deg}(y)\) se tornar \(1\), adicione \(y\) à fila.

O número de consultas é \(1\) (para graus) \(+\ 3 \times \lceil \log_3 n \rceil\) (para as divisões ternárias). Para \(n=5 \times 10^4\), \(\lceil \log_3 5 \times 10^4 \rceil = 10\). Portanto, \(1 + 3 \times 10 = 31\) consultas, o que está dentro do limite.

#include <iostream>
#include <vector>
#include <numeric> // Para std::iota
#include <algorithm> // Para std::reverse
#include <array>     // Para std::array
#include <queue>     // Para std::queue

// Função principal para descobrir as arestas da árvore
void descobrir_arestas_arvore() {
    int n_nodes_g;
    std::cin >> n_nodes_g;

    // Calcular o número de dígitos ternários necessários
    int radix_digits = 0;
    long long base_multiplier = 1;
    while (base_multiplier < n_nodes_g) {
        base_multiplier *= 3;
        ++radix_digits;
    }

    // Armazenar potências de 3 (para dígitos ternários)
    std::vector<long long> powers_of_3(radix_digits);
    powers_of_3[0] = 1;
    for (int i = 1; i < radix_digits; ++i) {
        powers_of_3[i] = powers_of_3[i - 1] * 3;
    }

    // Gerar todas as permutações para consultas
    std::vector<std::vector<int>> permutation_queries;
    permutation_queries.reserve(radix_digits * 3 + 1);

    for (int i = 0; i < radix_digits; ++i) {
        // Dividir nós com base no i-ésimo dígito ternário
        std::array<std::vector<int>, 3> groups_by_digit;
        for (int j = 1; j <= n_nodes_g; ++j) {
            groups_by_digit[((j - 1) / powers_of_3[i]) % 3].push_back(j);
        }

        // Criar 3 permutações cíclicas para cada dígito ternário
        for (int j = 0; j < 3; ++j) {
            std::vector<int> current_permutation_vec;
            current_permutation_vec.reserve(n_nodes_g);

            for (int k = 0; k < 3; ++k) {
                const auto& group = groups_by_digit[(j + k) % 3];
                current_permutation_vec.insert(current_permutation_vec.end(), group.begin(), group.end());
            }
            permutation_queries.push_back(current_permutation_vec);
        }
    }

    // Adicionar a permutação reversa para calcular graus
    auto full_sequence_perm = permutation_queries[0]; // [1, 2, ..., n] (ou similar, se permutation_queries[0] já for assim)
    std::vector<int> reversed_perm(n_nodes_g);
    std::iota(reversed_perm.begin(), reversed_perm.end(), 1); // [1, 2, ..., n]
    std::reverse(reversed_perm.begin(), reversed_perm.end()); // [n, n-1, ..., 1]
    
    permutation_queries.push_back(full_sequence_perm); // Primeira consulta para graus
    permutation_queries.push_back(reversed_perm); // Consulta reversa para graus
    

    int num_queries_made = permutation_queries.size();
    std::cout << num_queries_made << std::endl; // Informa o número total de consultas

    // Imprime todas as permutações para a máquina
    for (const auto& perm_vec : permutation_queries) {
        for (int i = 0; i < n_nodes_g; ++i) {
            std::cout << perm_vec[i] << (i == n_nodes_g - 1 ? "" : " ");
        }
        std::cout << std::endl;
    }

    // Ler resultados das consultas
    std::vector<std::vector<int>> query_results_diffs(num_queries_made, std::vector<int>(n_nodes_g + 1));
    for (int i = 0; i < num_queries_made; ++i) {
        long long prev_edges = 0;
        for (int j = 0; j < n_nodes_g; ++j) {
            long long current_edges;
            std::cin >> current_edges;
            if (current_edges == -1) { // Erro ou fim de interação
                return;
            }
            query_results_diffs[i][permutation_queries[i][j]] = current_edges - prev_edges;
            prev_edges = current_edges;
        }
    }

    // Calcular graus dos vértices
    std::vector<int> node_degrees(n_nodes_g + 1);
    // As últimas duas consultas foram P1=[1..N] e P2=[N..1]
    // A soma das arestas adicionadas por u em P1 e P2 dá o grau de u
    for (int i = 1; i <= n_nodes_g; ++i) {
        node_degrees[i] = query_results_diffs[num_queries_made - 2][i] + query_results_diffs[num_queries_made - 1][i];
    }
    
    // Calcular soma dos IDs dos vizinhos para cada nó, ponderado por dígitos ternários
    std::vector<long long> neighbor_id_sum_encoded(n_nodes_g + 1);

    for (int i = 0; i < radix_digits; ++i) {
        int q_idx0 = i * 3, q_idx1 = q_idx0 + 1, q_idx2 = q_idx0 + 2;
        long long current_radix_multiplier = powers_of_3[i];

        for (int j = 1; j <= n_nodes_g; ++j) {
            // Contagens de arestas para este nó 'j' nas 3 permutações cíclicas para o dígito 'i'
            long long c0 = query_results_diffs[q_idx0][j];
            long long c1 = query_results_diffs[q_idx1][j];
            long long c2 = query_results_diffs[q_idx2][j];
            
            // Diferenças nas contagens
            long long diff01 = c0 - c1;
            long long diff12 = c1 - c2;
            long long diff20 = c2 - c0;
            
            long long current_node_deg = node_degrees[j];
            std::array<long long, 3> neighbor_counts = {0, 0, 0}; // N_j(0, k), N_j(1, k), N_j(2, k)

            // Determinar o número de vizinhos com cada dígito ternário na posição 'i'
            switch (((j - 1) / current_radix_multiplier) % 3) {
                case 0: { // Nó 'j' tem dígito 0 na pos 'i'
                    // neighbor_counts[0] + neighbor_counts[1] + neighbor_counts[2] = current_node_deg
                    // neighbor_counts[0] - neighbor_counts[1] = diff01
                    // neighbor_counts[1] - neighbor_counts[2] = diff12
                    // neighbor_counts[2] - neighbor_counts[0] = diff20
                    // simplified: neighbor_counts[1] = (diff01 - diff20 + current_node_deg) / 3
                    // neighbor_counts[2] = (diff12 - diff01 + current_node_deg) / 3
                    neighbor_counts[1] = (diff01 + 2 * diff12 + current_node_deg) / 3;
                    neighbor_counts[2] = (2 * diff20 + diff01 + current_node_deg) / 3;
                    neighbor_counts[0] = current_node_deg - neighbor_counts[1] - neighbor_counts[2];
                } break;
                case 1: { // Nó 'j' tem dígito 1 na pos 'i'
                    neighbor_counts[0] = (2 * diff01 + diff20 + current_node_deg) / 3;
                    neighbor_counts[2] = (2 * diff12 + diff01 + current_node_deg) / 3;
                    neighbor_counts[1] = current_node_deg - neighbor_counts[0] - neighbor_counts[2];
                } break;
                case 2: { // Nó 'j' tem dígito 2 na pos 'i'
                    neighbor_counts[0] = (diff01 + 2 * diff20 + current_node_deg) / 3;
                    neighbor_counts[1] = (diff12 + 2 * diff01 + current_node_deg) / 3;
                    neighbor_counts[2] = current_node_deg - neighbor_counts[0] - neighbor_counts[1];
                } break;
            }
            
            // Codificar a soma dos IDs dos vizinhos para este nó 'j'
            // Cada neighbor_counts[d] * d * current_radix_multiplier
            neighbor_id_sum_encoded[j] += (neighbor_counts[1] * 1 + neighbor_counts[2] * 2) * current_radix_multiplier;
        }
    }

    // Calcula bv[i] = (soma dos IDs dos vizinhos de i) + deg[i]
    // Isso é feito para que, quando um nó 'x' (folha) é processado, bv[x] contenha o ID de seu pai 'y'.
    // A ideia é que se x é folha e seu pai é y, então a soma dos IDs dos vizinhos de x é apenas y.
    // Assim, neighbor_id_sum_encoded[x] = y, e bv[x] = y + deg[x].
    // Mas note que neighbor_id_sum_encoded é a SOMA dos vizinhos, não o ID do pai diretamente.
    // É usado no processo de poda.
    std::vector<long long> node_bv(n_nodes_g + 1);
    for (int i = 1; i <= n_nodes_g; ++i) {
        node_bv[i] = neighbor_id_sum_encoded[i];
    }
    
    std::queue<int> leaf_queue;
    for (int i = 1; i <= n_nodes_g; ++i) {
        if (node_degrees[i] == 1) {
            leaf_queue.push(i);
        }
    }

    int edges_found_count = 0;
    while (!leaf_queue.empty() && edges_found_count < n_nodes_g - 1) {
        int leaf_x = leaf_queue.front();
        leaf_queue.pop();

        if (node_degrees[leaf_x] != 1) { // Já foi processado ou não é mais folha
            continue;
        }

        int parent_y = node_bv[leaf_x]; // O ID do pai y deve ser a soma codificada dos vizinhos de leaf_x.
                                        // Como leaf_x é folha, seu único vizinho é y.
        std::cout << leaf_x << " " << parent_y << std::endl;

        ++edges_found_count;
        node_degrees[leaf_x]--; // Remove aresta de x
        node_degrees[parent_y]--; // Remove aresta de y

        // Atualizar node_bv para o pai 'y'
        // node_bv[y] deve "esquecer" que x era um vizinho
        node_bv[parent_y] -= leaf_x; // Isso é um truque para remover o ID de x da soma dos vizinhos de y

        if (node_degrees[parent_y] == 1) {
            leaf_queue.push(parent_y);
        }
    }
}

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

    int num_test_cases;
    std::cin >> num_test_cases;

    while (num_test_cases--) {
        descobrir_arestas_arvore();
    }

    return 0;
}