Técnicas de Árvores Link-Cut: Implementação e Aplicações

As Árvores Link-Cut (LCT) são uma estrutura de dados dinâmica baseada em decomposição de cadeias reais, projetada para manter uma floresta de árvores. Em uma LCT, cada nó possui uma aresta real para um de seus filhos e arestas virtuais para os outros. Essas arestas podem mudar dinamicamente, e uma árvore Splay é usada para manter cada cadeia de arestas reais conectadas.

As LCT suportam diversas operações:

Consulta e modificação de informações em cadeias
Troca de raiz
Adição e remoção dinâmica de arestas, fusão/separação de árvores
Manutenção dinâmica de conectividade
Outras operações avançadas

Propriedades Principais

Cada Splay mantém um caminho da raiz para um nó específico, com profundidades estritamente crescentes na árvore orgiinal. A sequência de profundidades obtida pelo percurso em ordem média é estritamente crescente.
Cada nó pertence e pertence apenas a um Splay.
As arestas são classificadas como reais ou virtuais. As arestas reais estão dentro do Splay, enquanto as arestas virtuais conectam a raiz de um Splay ao pai do nó mais à esquerda no percurso em ordem média daquele Splay na árvore original.
Quando um nó tem múltiplos filhos, apenas uma aresta pode ser real, enquanto as outras devem ser virtuais para manter as propriedades da árvore.

Operações Básicas

Access

Objetivo: Obter um Splay onde o percurso em ordem média começa na raiz da árvore original e termina no nó especificado.

void Acessar(int x) {
    int y = 0;
    while (x) {
        RotacionarParaRaiz(x);
        filhoDireito[x] = y;
        Atualizar(x);
        y = x;
        x = pai[x];
    }
}

MakeRoot

Objetivo: Transformar um nó específico na raiz da árvore original.

FindRoot

Objetivo: Encontrar a raiz da árvore original que contém o nó especificado.

int EncontrarRaiz(int x) {
    Acessar(x);
    RotacionarParaRaiz(x);
    while (filhoEsquerdo[x]) {
        Propagar(x);
        x = filhoEsquerdo[x];
    }
    RotacionarParaRaiz(x);
    return x;
}

Split

Objetivo: Extrair o caminho entre dois nós x e y como um Splay.

void Separar(int x, int y) {
    TornarRaiz(x);
    Acessar(y);
    RotacionarParaRaiz(y);
}

Link

Objetivo: Adicionar uma aresta entre dois nós.

void Conectar(int x, int y) {
    TornarRaiz(x);
    if (EncontrarRaiz(y) != x) {
        pai[x] = y;
    }
}

Cut

Objetivo: Remover a aresta entre dois nós.

void Cortar(int x, int y) {
    TornarRaiz(x);
    if (EncontrarRaiz(y) == x && pai[y] == x && !filhoEsquerdo[y]) {
        pai[y] = 0;
        filhoDireito[x] = 0;
        Atualizar(x);
    }
}

Implementação Template

Código para suportar operações de adição/remoção de arestas e consulta/modificação de valores de nós:

// Estrutura básica para LCT
#define filhoEsquerdo arvore[x][0]
#define filhoDireito arvore[x][1]
const int MAX_N = 300010;
int pai[MAX_N], arvore[MAX_N][2], valor[MAX_N], soma[MAX_N];
bool marcacao[MAX_N];

bool EhRaiz(int x) {
    return (pai[x] == 0) || (arvore[pai[x]][0] != x && arvore[pai[x]][1] != x);
}

void Atualizar(int x) {
    soma[x] = soma[filhoEsquerdo] ^ soma[filhoDireito] ^ valor[x];
}

void Inverter(int x) {
    int temp = filhoEsquerdo;
    filhoEsquerdo = filhoDireito;
    filhoDireito = temp;
    marcacao[x] ^= 1;
}

void Propagar(int x) {
    if (marcacao[x]) {
        if (filhoEsquerdo) Inverter(filhoEsquerdo);
        if (filhoDireito) Inverter(filhoDireito);
        marcacao[x] = false;
    }
}

void Rotacionar(int x) {
    int y = pai[x], z = pai[y], direcao = arvore[y][1] == x;
    if (EhRaiz(y)) arvore[z][arvore[z][1] == y] = x;
    arvore[x][!direcao] = y;
    arvore[y][direcao] = arvore[x][!direcao];
    if (arvore[x][!direcao]) pai[arvore[x][!direcao]] = y;
    pai[y] = x;
    pai[x] = z;
    Atualizar(y);
}

void RotacionarParaRaiz(int x) {
    int y = x;
    std::vector<int> pilha;
    while (!EhRaiz(y)) {
        pilha.push_back(y);
        y = pai[y];
    }
    pilha.push_back(y);
    for (int i = pilha.size() - 1; i >= 0; i--) Propagar(pilha[i]);
    
    while (!EhRaiz(x)) {
        y = pai[x];
        int z = pai[y];
        if (!EhRaiz(y)) {
            if ((arvore[y][0] == x) ^ (arvore[z][0] == y))
                Rotacionar(x);
            else
                Rotacionar(y);
        }
        Rotacionar(x);
    }
    Atualizar(x);
}

void Acessar(int x) {
    int y = 0;
    while (x) {
        RotacionarParaRaiz(x);
        filhoDireito[x] = y;
        Atualizar(x);
        y = x;
        x = pai[x];
    }
}

void TornarRaiz(int x) {
    Acessar(x);
    RotacionarParaRaiz(x);
    Inverter(x);
}

int EncontrarRaiz(int x) {
    Acessar(x);
    RotacionarParaRaiz(x);
    while (filhoEsquerdo) {
        Propagar(x);
        x = filhoEsquerdo;
    }
    RotacionarParaRaiz(x);
    return x;
}

void Separar(int x, int y) {
    TornarRaiz(x);
    Acessar(y);
    RotacionarParaRaiz(y);
}

void Conectar(int x, int y) {
    TornarRaiz(x);
    if (EncontrarRaiz(y) != x) pai[x] = y;
}

void Cortar(int x, int y) {
    TornarRaiz(x);
    if (EncontrarRaiz(y) == x && pai[y] == x && !filhoEsquerdo[y]) {
        pai[y] = 0;
        filhoDireito[x] = 0;
        Atualizar(x);
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &valor[i]);
    
    while (m--) {
        int op, x, y;
        scanf("%d %d %d", &op, &x, &y);
        if (op == 0) {
            Separar(x, y);
            printf("%d\n", soma[y]);
        } else if (op == 1) {
            Conectar(x, y);
        } else if (op == 2) {
            Cortar(x, y);
        } else if (op == 3) {
            RotacionarParaRaiz(x);
            valor[x] = y;
        }
    }
    return 0;
}</int>

Aplicações

Manutenção de Informações em Cadeias

As LCT são particularmente úteis para manter informações sobre caminhos em árvores dinâmicas. Por exemplo, no problema "Ovelhas Saltitantes", onde cada ponto i tem um valor k_i que indica para qual ponto ele pula, podemos modelar as transições como arestas em uma árvore e usar LCT para consultar o número de saltos necessários para sair da árvore.

const int MAX_N = 100010;
int pai[MAX_N], arvore[MAX_N][2], tamanho[MAX_N];

bool EhRaiz(int x) {
    return (pai[x] == 0) || (arvore[pai[x]][0] != x && arvore[pai[x]][1] != x);
}

void Atualizar(int x) {
    tamanho[x] = tamanho[filhoEsquerdo] + tamanho[filhoDireito] + 1;
}

void Rotacionar(int x) {
    int y = pai[x], z = pai[y], direcao = arvore[y][1] == x;
    if (EhRaiz(y)) arvore[z][arvore[z][1] == y] = x;
    arvore[x][!direcao] = y;
    arvore[y][direcao] = arvore[x][!direcao];
    if (arvore[x][!direcao]) pai[arvore[x][!direcao]] = y;
    pai[y] = x;
    pai[x] = z;
    Atualizar(y);
}

void RotacionarParaRaiz(int x) {
    int y = x;
    while (!EhRaiz(y)) y = pai[y];
    std::vector<int> pilha;
    while (x) {
        pilha.push_back(x);
        x = pai[x];
    }
    for (int i = pilha.size() - 1; i >= 0; i--) {
        int u = pilha[i];
        if (pai[u]) Propagar(pai[u]);
    }
    for (int i = pilha.size() - 1; i >= 0; i--) {
        int u = pilha[i];
        if (!EhRaiz(u)) {
            int v = pai[u];
            int w = pai[v];
            if (!EhRaiz(v)) {
                if ((arvore[v][0] == u) ^ (arvore[w][0] == v))
                    Rotacionar(u);
                else
                    Rotacionar(v);
            }
            Rotacionar(u);
        }
        Atualizar(u);
    }
}

void Acessar(int x) {
    int y = 0;
    while (x) {
        RotacionarParaRaiz(x);
        filhoDireito[x] = y;
        Atualizar(x);
        y = x;
        x = pai[x];
    }
}

int main() {
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        tamanho[i] = 1;
        int k;
        scanf("%d", &k);
        if (i + k <= n) pai[i] = i + k;
    }
    scanf("%d", &m);
    while (m--) {
        int op, x, y;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d", &x);
            x++;
            Acessar(x);
            RotacionarParaRaiz(x);
            printf("%d\n", tamanho[x]);
        } else {
            scanf("%d %d", &x, &y);
            x++;
            Acessar(x);
            RotacionarParaRaiz(x);
            if (filhoEsquerdo) {
                pai[filhoEsquerdo] = 0;
                filhoEsquerdo = 0;
                Atualizar(x);
            }
            if (x + y <= n) pai[x] = x + y;
        }
    }
    return 0;
}</int>

Manutenção de Conectividade

Para verificar se dois nós estão na mesma árvore, podemos usar a operação FindRoot. Se as raízes são iguais, os nós estão conectados.

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    std::vector<:pair int="">> eventos;
    
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        Conectar(u, v);
    }
    
    while (m--) {
        char op[5];
        scanf("%s", op);
        if (op[0] == 'Q') {
            int u, v;
            scanf("%d %d", &u, &v);
            TornarRaiz(u);
            puts(EncontrarRaiz(v) == u ? "Sim" : "Não");
        } else if (op[0] == 'C') {
            int u, v;
            scanf("%d %d", &u, &v);
            eventos.emplace_back(u, v);
            Cortar(u, v);
        } else {
            int idx;
            scanf("%d", &idx);
            auto [u, v] = eventos[idx];
            Conectar(u, v);
        }
    }
    return 0;
}</:pair>

Manutenção de Ponderação de Arestas

Para problemas envolvendo pesos nas arestas, podemos transformar cada aresta em um nó intermediário conectado aos seus dois endpoints.

const int MAX_N = 50010, MAX_M = 200010, MAX_P = MAX_N + MAX_M;
int pai[MAX_P], arvore[MAX_P][2], minAresta[MAX_P], valor[MAX_P], n, m;
bool visitada[MAX_M];
int componente[MAX_P];

int EncontrarComponente(int x) {
    return x == componente[x] ? x : componente[x] = EncontrarComponente(componente[x]);
}

void Rotacionar(int x) {
    int y = pai[x], z = pai[y], direcao = arvore[y][1] == x;
    if (pai[y]) arvore[z][arvore[z][1] == y] = x;
    arvore[x][!direcao] = y;
    arvore[y][direcao] = arvore[x][!direcao];
    if (arvore[x][!direcao]) pai[arvore[x][!direcao]] = y;
    pai[y] = x;
    pai[x] = z;
    Atualizar(y);
}

void RotacionarParaRaiz(int x) {
    int y = x;
    while (pai[y]) y = pai[y];
    std::vector<int> pilha;
    while (x) {
        pilha.push_back(x);
        x = pai[x];
    }
    for (int i = pilha.size() - 1; i >= 0; i--) {
        if (pai[pilha[i]]) Propagar(pai[pilha[i]]);
    }
    for (int i = pilha.size() - 1; i >= 0; i--) {
        int u = pilha[i];
        if (!EhRaiz(u)) {
            int v = pai[u];
            int w = pai[v];
            if (!EhRaiz(v)) {
                if ((arvore[v][0] == u) ^ (arvore[w][0] == v))
                    Rotacionar(u);
                else
                    Rotacionar(v);
            }
            Rotacionar(u);
        }
        Atualizar(u);
    }
}

void Acessar(int x) {
    int y = 0;
    while (x) {
        RotacionarParaRaiz(x);
        arvore[x][1] = y;
        Atualizar(x);
        y = x;
        x = pai[x];
    }
}

void ConectarAresta(int idx) {
    int u = arestas[idx].primeiro, v = arestas[idx].segundo;
    TornarRaiz(u);
    if (EncontrarComponente(u) != EncontrarComponente(v)) {
        componente[pai[arestas[idx].indice] = u] = v;
    }
}

void CortarAresta(int x) {
    Acessar(arestas[x - MAX_N].primeiro);
    RotacionarParaRaiz(x);
    arvore[x][0] = arvore[x][1] = pai[arvore[x][0]] = pai[arvore[x][1]] = 0;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        componente[i] = i;
        valor[i] = INF;
    }
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &arestas[i].primeiro, &arestas[i].segundo, &arestas[i].peso);
        valor[i + MAX_N] = arestas[i].peso;
        minAresta[i + MAX_N] = i + MAX_N;
    }
    
    std::sort(arestas + 1, arestas + m + 1);
    int cnt = 1, ponta = 1, u, v, resposta = INF;
    
    for (int i = 1; i <= m; i++) {
        u = arestas[i].primeiro;
        v = arestas[i].segundo;
        int compU = EncontrarComponente(u);
        int compV = EncontrarComponente(v);
        
        if (compU != compV) {
            visitada[i] = true;
            ConectarAresta(i);
            componente[compU] = compV;
            cnt++;
            if (cnt == n) resposta = std::min(resposta, arestas[i].peso - arestas[ponta].peso);
        } else {
            if (u == v) continue;
            visitada[i] = true;
            TornarRaiz(u);
            Acessar(v);
            RotacionarParaRaiz(v);
            int minArestaCiclo = minAresta[v];
            while (!visitada[ponta]) ponta++;
            if (arestas[minArestaCiclo - MAX_N].peso - arestas[ponta].peso < resposta) {
                resposta = arestas[minArestaCiclo - MAX_N].peso - arestas[ponta].peso;
            }
            CortarAresta(minArestaCiclo);
            ConectarAresta(i);
        }
    }
    
    printf("%d\n", resposta);
    return 0;
}</int>

Manutenção de Informações de Subárvores Virtuais

Para manter informações sobre subárvores virtuais, precisamos manter tanto a soma das subárvores virtuais quanto a soma total. A soma total é simplesmente a soma das subárvores virtuais e dos valores dos nós.

const int MAX_N = 100010;
int pai[MAX_N], arvore[MAX_N][2], somaTotal[MAX_N], somaVirtual[MAX_N];
bool marcacao[MAX_N];

bool EhRaiz(int x) {
    return (pai[x] == 0) || (arvore[pai[x]][0] != x && arvore[pai[x]][1] != x);
}

void Atualizar(int x) {
    somaTotal[x] = somaTotal[arvore[x][0]] + somaTotal[arvore[x][1]] + somaVirtual[x] + 1;
}

void Inverter(int x) {
    std::swap(arvore[x][0], arvore[x][1]);
    marcacao[x] ^= 1;
}

void Propagar(int x) {
    if (marcacao[x]) {
        if (arvore[x][0]) Inverter(arvore[x][0]);
        if (arvore[x][1]) Inverter(arvore[x][1]);
        marcacao[x] = false;
    }
}

void Rotacionar(int x) {
    int y = pai[x], z = pai[y], direcao = arvore[y][1] == x;
    if (pai[y]) arvore[z][arvore[z][1] == y] = x;
    arvore[x][!direcao] = y;
    arvore[y][direcao] = arvore[x][!direcao];
    if (arvore[x][!direcao]) pai[arvore[x][!direcao]] = y;
    pai[y] = x;
    pai[x] = z;
    Atualizar(y);
}

void RotacionarParaRaiz(int x) {
    int y = x;
    std::vector<int> pilha;
    while (!EhRaiz(y)) {
        pilha.push_back(y);
        y = pai[y];
    }
    pilha.push_back(y);
    for (int i = pilha.size() - 1; i >= 0; i--) Propagar(pilha[i]);
    
    while (!EhRaiz(x)) {
        y = pai[x];
        int z = pai[y];
        if (!EhRaiz(y)) {
            if ((arvore[y][0] == x) ^ (arvore[z][0] == y))
                Rotacionar(x);
            else
                Rotacionar(y);
        }
        Rotacionar(x);
    }
    Atualizar(x);
}

void Acessar(int x) {
    int y = 0;
    while (x) {
        RotacionarParaRaiz(x);
        somaVirtual[x] += somaTotal[arvore[x][1]];
        somaVirtual[x] -= somaTotal[arvore[x][1] = y];
        Atualizar(x);
        y = x;
        x = pai[x];
    }
}

void TornarRaiz(int x) {
    Acessar(x);
    RotacionarParaRaiz(x);
    Inverter(x);
}

void Separar(int x, int y) {
    TornarRaiz(x);
    Acessar(y);
    RotacionarParaRaiz(y);
}

void Conectar(int x, int y) {
    Separar(x, y);
    somaVirtual[pai[x] = y] += somaTotal[x];
    Atualizar(y);
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++) {
        somaTotal[i] = 1;
    }
    
    while (m--) {
        char op[5];
        scanf("%s", op);
        int x, y;
        scanf("%d %d", &x, &y);
        
        if (op[0] == 'A') {
            Conectar(x, y);
        } else {
            Separar(x, y);
            long long resultado = (long long)(somaVirtual[x] + 1) * (somaVirtual[y] + 1);
            printf("%lld\n", resultado);
        }
    }
    
    return 0;
}</int>

Tags: estrutura-de-dados arvores-dinamicas splay lct Algoritmos

Publicado em 6-30 18:10

Doido Dev