Determinar o caminho simples entre dois nós em uma árvore que resulte no valor máximo de XOR acumulado das arestas é um problema clássico que combina teoria de grafos e estruturas de dados efiicentes. A solução baseia-se em uma propriedade fundamental da operação XOR e no uso de uma Trie Binária para otimizar a busca.

A Propriedade do XOR em Árvores

Para qualquer par de nós $(u, v)$ em uma árvore, o XOR do caminho entre eles pode ser simplificado. Se definirmos $P(x)$ como o valor do XOR acumulado da raiz até o nó $x$, o XOR do caminho entre $u$ e $v$ é dado por:

XOR(u, v) = P(u) ^ P(v)

Isso acontece porque o trecho do caminho que vai da raiz até o Ancestral Comum Mais Próximo (LCA) de $u$ e $v$ é percorrido "duas vezes" na expressão, resultando em zero e restando apenas o caminho direto entre os dois nós. Com isso, o problema de encontrar o caminho máximo se transforma em encontrar dois valores no conjunto $\{P(1), P(2), \dots, P(n)\}$ cujo XOR seja máximo.

Estrutura de Dados: Trie Binária

Para encontrar o par com o maior XOR de forma eficiente, inserimos todos os valores $P(i)$ em uma Trie Binária. Para cada valor $P(u)$, buscamos na Trie o caminho que mais se opõe aos seus bits (do mais significativo para o menos significativo). Se o bit atual de $P(u)$ for 0, tentamos seguir pelo ramo 1; se for 1, tentamos o ramo 0.

Exemplo de Implementação: Caminho Máximo Estático

Abaixo, apresentamos uma implementação para o problema clássico de encontrar a maior distância XOR em uma árvore:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_BITS = 30;
const int MAX_NODES = 100005;

struct Node {
    int filhos[2];
    Node() { filhos[0] = filhos[1] = 0; }
};

vector<Node> trie(MAX_NODES * MAX_BITS);
int proximo_no = 1;

void inserir(int val) {
    int atual = 0;
    for (int i = MAX_BITS; i >= 0; --i) {
        int bit = (val >> i) & 1;
        if (!trie[atual].filhos[bit]) {
            trie[atual].filhos[bit] = proximo_no++;
        }
        atual = trie[atual].filhos[bit];
    }
}

int buscar_maximo(int val) {
    int atual = 0;
    int resultado = 0;
    for (int i = MAX_BITS; i >= 0; --i) {
        int bit = (val >> i) & 1;
        int oposto = bit ^ 1;
        if (trie[atual].filhos[oposto]) {
            resultado |= (1 << i);
            atual = trie[atual].filhos[oposto];
        } else {
            atual = trie[atual].filhos[bit];
        }
    }
    return resultado;
}

vector<pair<int, int>> adj[MAX_NODES];
int prefix_xor[MAX_NODES];

void dfs(int u, int p, int atual_xor) {
    prefix_xor[u] = atual_xor;
    for (auto& edge : adj[u]) {
        if (edge.first != p) {
            dfs(edge.first, u, atual_xor ^ edge.second);
        }
    }
}

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

    dfs(1, 0, 0);

    for (int i = 1; i <= n; ++i) inserir(prefix_xor[i]);

    int max_res = 0;
    for (int i = 1; i <= n; ++i) {
        max_res = max(max_res, buscar_maximo(prefix_xor[i]));
    }

    cout << max_res << endl;
    return 0;
}

Variações com Paridade e Atualizações Dinâmicas

Em cenários mais copmlexos, pode ser necessário considerar a paridade da quantidade de arestas no caminho. Se o número de arestas entre $u$ e $v$ for par, certas operações globais podem se anular. Para gerenciar isso, podemos manter duas Tries ou adicionar um marcador de profundidade durante a DFS para distinguir caminhos com número par ou ímpar de arestas.

Quando existe uma operação de atualização que aplica XOR em todos os caminhos, geralmente um valor global pode ser mantido e levado em conta durante a consulta na Trie, sem a necessidade de reconstruir a estrutura inteira.

// Estrutura para busca considerando paridade (exemplo conceitual)
int consultar_com_paridade(int val_alvo, int paridade_alvo, int mod_global) {
    // Busca na sub-trie que armazena apenas nós com a paridade desejada
    // val_alvo pode ser ajustado pelo mod_global se a operação afetar caminhos ímpares
    return buscar_na_trie_especifica(val_alvo ^ mod_global, paridade_alvo);
}

A técnica da Trie Binária reduz a complexidade da busca de $O(N^2)$ para $O(N \cdot \text{bits})$, tornando viável a resolução em árvores com centenas de milhares de nós.