Este artigo aborda dois problemmas de jogos combinatórios em árvores que utilizam a função Sprague-Grundy (SG). O primeiro envolve a remoção de subárvores, enquanto o segundo foca na coloração de caminhos até a raiz.

AGC017D - Jogo em Árvore

Problema: Dada uma árvore enraizada no nó 1, dois jogadores removem alternadamente uma subárvore (exceto a árvore enteira). Vence quem fizer a última jogada. Quem vence com jogadas ótimas?

Solução: Calcula-se o valer SG para cada nó. A chave é que cada subárvore filha equivale a um jogo independente. Ao adicionar um nó pai a uma subárvore, seu valor SG aumenta em 1. Para um nó pai, o valor SG é o XOR dos valores (SG do filho + 1) de todos os filhos.

valor_sg[pai] = ⨁ (valor_sg[filho] + 1)

Prova por indução: Caso base (1 nó: SG=0). Adicionar um nó pai cria operações equivalentes a subárvores com SG incrementado, resultando em SG original + 1.

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 100050;
int valor_sg[MAX_N];
vector<int> adjacencia[MAX_N];

void DFS(int u, int pai) {
    for (int v : adjacencia[u]) {
        if (v == pai) continue;
        DFS(v, u);
        valor_sg[u] ^= (valor_sg[v] + 1);
    }
}

int main() {
    int n, u, v;
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        adjacencia[u].push_back(v);
        adjacencia[v].push_back(u);
    }
    DFS(1, 0);
    cout << (valor_sg[1] ? "Alice" : "Bob") << endl;
    return 0;
}

SPOJ11414 - Combate em Árvore

Problema: Árvore com nós brancos/pretos. Jogadores alternam turnos, escolhendo um nó branco e pintando de preto seu caminho até a raiz. Quais movimentos iniciais garantem vitória à Alice?

Solução: Cada operação divide a árvore em subárvores independentes. Calcula-se o SG usando uma trie binária para operações de XOR e mex. A trie armazena estados de florestas, permitindo mesclagem eficiente durante o DFS.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 100050;
const int MAX_TRIE = MAX_N * 23;
int cor[MAX_N], valor_sg[MAX_N], xor_filhos[MAX_N];
vector<int> adjacencia[MAX_N];
int respostas[MAX_N], contador_respostas;
int total_nos, filhos_trie[MAX_TRIE][2], raiz_trie[MAX_N];
int marcador[MAX_TRIE], tamanho[MAX_TRIE];

void propagar(int no, int k) {
    if ((marcador[no] >> (k-1)) & 1) 
        swap(filhos_trie[no][0], filhos_trie[no][1]);
    if (filhos_trie[no][0]) marcador[filhos_trie[no][0]] ^= marcador[no];
    if (filhos_trie[no][1]) marcador[filhos_trie[no][1]] ^= marcador[no];
    marcador[no] = 0;
}

int mesclar(int raiz1, int raiz2, int k) {
    if (!raiz1 || !raiz2) return raiz1 ? raiz1 : raiz2;
    if (k == 0) {
        tamanho[raiz1] |= tamanho[raiz2];
        return raiz1;
    }
    propagar(raiz1, k);
    propagar(raiz2, k);
    filhos_trie[raiz1][0] = mesclar(filhos_trie[raiz1][0], filhos_trie[raiz2][0], k-1);
    filhos_trie[raiz1][1] = mesclar(filhos_trie[raiz1][1], filhos_trie[raiz2][1], k-1);
    tamanho[raiz1] = tamanho[filhos_trie[raiz1][0]] + tamanho[filhos_trie[raiz1][1]];
    return raiz1;
}

int calcular_mex(int raiz) {
    int resultado = 0;
    for (int k = 20; k >= 0; k--) {
        propagar(raiz, k);
        if (tamanho[filhos_trie[raiz][0]] != (1 << k)) 
            raiz = filhos_trie[raiz][0];
        else {
            resultado += (1 << k);
            raiz = filhos_trie[raiz][1];
        }
    }
    return resultado;
}

void DFS(int u, int pai) {
    for (int v : adjacencia[u]) {
        if (v == pai) continue;
        DFS(v, u);
        xor_filhos[u] ^= valor_sg[v];
    }
    if (!cor[u]) {
        int no = raiz_trie[u];
        tamanho[no]++;
        for (int k = 20; k >= 0; k--) {
            propagar(no, k);
            int bit = (xor_filhos[u] >> k) & 1;
            if (!filhos_trie[no][bit]) filhos_trie[no][bit] = ++total_nos;
            no = filhos_trie[no][bit];
            tamanho[no]++;
        }
    }
    for (int v : adjacencia[u]) {
        if (v == pai) continue;
        marcador[raiz_trie[v]] ^= xor_filhos[u] ^ valor_sg[v];
        raiz_trie[u] = mesclar(raiz_trie[u], raiz_trie[v], 21);
    }
    valor_sg[u] = calcular_mex(raiz_trie[u]);
}

void buscar_movimentos(int u, int pai, int valor) {
    if (!cor[u] && !valor) 
        respostas[contador_respostas++] = u;
    for (int v : adjacencia[u]) {
        if (v == pai) continue;
        buscar_movimentos(v, pai, valor ^ valor_sg[v] ^ xor_filhos[v]);
    }
}

int main() {
    cin >> n;
    total_nos = n;
    for (int i = 1; i <= n; i++) {
        cin >> cor[i];
        raiz_trie[i] = i;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adjacencia[u].push_back(v);
        adjacencia[v].push_back(u);
    }
    DFS(1, 0);
    buscar_movimentos(1, 0, xor_filhos[1]);
    if (!contador_respostas) cout << "-1";
    else {
        sort(respostas, respostas + contador_respostas);
        for (int i = 0; i < contador_respostas; i++) 
            cout << respostas[i] << "\n";
    }
    return 0;
}