O Princípio da Inclusão-Exclusão é uma ferramenta combinatória poderosa para resolver problemas de contagem complexos, especialmente quando as condições a serem satisfeitas se sobrepõem. Frequentemente, a contagem direta de elementos que satisfazem *todas* as condições é difícil. Em vez disso, podemos contar elementos que satisfazem *algumas* condições e usar um coeficiente para corrigir as contagens duplicadas ou ausentes. Uma forma alternativa de visualizar ou implementar o Princípio da Inclusão-Exclusão para certas estruturas (como conjuntos binários) é através da Transformada de Walsh-Hadamard (FWT), que pode converter somas com coeficientes em produtos de ponto, simplificando o cálculo.

Este artigo explora duas aplicações dsitintas do Princípio da Inclusão-Exclusão em problemas de grafos, utilizando o Teorema da Árvore Matriz e Programação Dinâmica (DP) em árvores.

Problema 1: Contagem de Árvores Geradoras com Restrições de Cores

Consideramos um problema onde é necessário construir uma árvore geradora que utilize exatamente uma aresta de cada "cor" (ou tipo de aresta) disponível. Um grafo pode ter múltiplos grupos de arestas, e queremos selecionar uma aresta de cada grupo para formar uma árvore geradora do grafo. A dificuldade surge porque a seleção de uma aresta de um grupo afeta a disponibilidade e a estrutura para os outros grupos.

A solução envolve o Princípio da Inclusão-Exclusão. Em vez de garantir que exatamente uma aresta de cada cor seja usada, iteramos sobre todos os subconjuntos de cores permitidas. Para cada subconjunto de cores \(S\), construímos um grafo auxiliar que contém apenas as arestas das cores em \(S\). Em seguida, contamos o número de árvores geradoras neste grafo auxiliar. O coeficiente de inclusão-exclusão, \((-1)^{(\text{total de cores} - |S|)}\), é aplicado a esta contagem.

O número de árvores geradoras em um grafo pode ser calculado usando o Teorema da Árvore Matriz de Kirchhoff. Este teorema afirma que o número de árvores geradoras de um grafo \(G\) é igual a qualquer cofator de sua matriz Laplaciana. A matriz Laplaciana \(L\) é definida como \(L = D - A\), onde \(D\) é a matriz de graus (diagonal, com \(D_{ii}\) sendo o grau do vértice \(i\)) e \(A\) é a matriz de adjacência. Para calcular o número de árvores geradoras, tomamos qualquer submatriz obtida removendo uma linha e uma coluna (por exemplo, a última linha e a última coluna) e calculamos seu determinante.

O algoritmo geral é:

1. Inicialize a resposta total como 0.
2. Itere sobre todos os \(2^{\text{num\_cores}}\) subconjuntos de cores.
3. Para cada subconjunto \(S\):
   1. Construa a matriz Lalpaciana para o grafo formado apenas pelas arestas das cores em \(S\). Os pesos das arestas são adicionados aos graus e subtraídos das entradas de adjacência.
   2. Calcule o determinante de uma submatriz (por exemplo, a submatriz \((N-1) \times (N-1)\), removendo a \(N\)-ésima linha e \(N\)-ésima coluna) da matriz Laplaciana.
   3. Multiplique o determinante pelo coeficiente de inclusão-exclusão e adicione à resposta total.
4. Ajuste a resposta final para garantir que seja positiva (usando operações de módulo).

#include <iostream>
#include <vector>
#include <numeric> // Para std::swap

const int MODULO_CONST = 1e9 + 7;
const int MAX_GRAPH_NODES = 20;

// Função para calcular (base^exp) % MODULO_CONST
long long powerModulo(long long base, long long exponent) {
    long long result = 1;
    base %= MODULO_CONST;
    while (exponent > 0) {
        if (exponent % 2 == 1) result = (result * base) % MODULO_CONST;
        base = (base * base) % MODULO_CONST;
        exponent /= 2;
    }
    return result;
}

// Função para calcular o determinante de uma matriz (matrixSize x matrixSize) usando eliminação Gaussiana
long long computeMatrixDeterminant(std::vector<std::vector<long long>>& inputMatrix, int matrixSize) {
    long long determinant = 1;

    for (int i = 0; i < matrixSize; ++i) {
        int pivotRow = i;
        for (int j = i + 1; j < matrixSize; ++j) {
            if (inputMatrix[j][i] != 0) { // Encontra um pivô não-zero
                pivotRow = j;
                break;
            }
        }

        if (inputMatrix[pivotRow][i] == 0) { // Se a coluna é toda zero abaixo do pivô, determinante é 0
            return 0;
        }

        if (pivotRow != i) { // Troca as linhas se o pivô não estiver na linha atual
            determinant = (MODULO_CONST - determinant) % MODULO_CONST; // Troca de linhas muda o sinal do determinante
            std::swap(inputMatrix[i], inputMatrix[pivotRow]);
        }

        long long inversePivot = powerModulo(inputMatrix[i][i], MODULO_CONST - 2); // Inverso multiplicativo modular

        determinant = (determinant * inputMatrix[i][i]) % MODULO_CONST; // Multiplica pelo pivô

        // Normaliza a linha atual
        for (int col = i; col < matrixSize; ++col) {
            inputMatrix[i][col] = (inputMatrix[i][col] * inversePivot) % MODULO_CONST;
        }

        // Elimina outras linhas abaixo
        for (int row = i + 1; row < matrixSize; ++row) {
            long long factor = inputMatrix[row][i];
            if (factor == 0) continue; // Já é zero
            for (int col = i; col < matrixSize; ++col) {
                inputMatrix[row][col] = (inputMatrix[row][col] - (inputMatrix[i][col] * factor) % MODULO_CONST + MODULO_CONST) % MODULO_CONST;
            }
        }
    }
    return determinant;
}

struct EdgeInfo {
    int nodeA, nodeB;
};

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

    int numGraphNodes;
    std::cin >> numGraphNodes;

    // Existem numGraphNodes - 1 "cores" de arestas (cada com múltiplos arcos)
    std::vector<int> numEdgesPerColor(numGraphNodes - 1); 
    std::vector<:vector>> edgeDataPerColor(numGraphNodes - 1);

    for (int i = 0; i < numGraphNodes - 1; ++i) { // Iterar sobre cada "cor"
        std::cin >> numEdgesPerColor[i];
        edgeDataPerColor[i].resize(numEdgesPerColor[i]);
        for (int j = 0; j < numEdgesPerColor[i]; ++j) {
            std::cin >> edgeDataPerColor[i][j].nodeA >> edgeDataPerColor[i][j].nodeB;
        }
    }

    long long finalAnswer = 0;

    // Iterar sobre todos os subconjuntos de 'cores' (representado por um bitmask)
    // O número de cores é (numGraphNodes - 1). Máscaras vão de 1 a 2^(numGraphNodes-1) - 1.
    for (int colorSetMask = 1; colorSetMask < (1 << (numGraphNodes - 1)); ++colorSetMask) {
        // A matriz Laplaciana opera em nós de 1 a numGraphNodes
        std::vector<:vector long="">> laplacianMatrix(numGraphNodes + 1, std::vector<long long="">(numGraphNodes + 1, 0));
        
        int subsetSize = 0; // Contar o número de bits setados para cálculo do sinal

        // Constrói a matriz Laplaciana para o subconjunto atual de cores
        for (int colorIdx = 0; colorIdx < numGraphNodes - 1; ++colorIdx) {
            if ((colorSetMask >> colorIdx) & 1) { // Se esta cor está no subconjunto atual
                subsetSize++;
                for (const auto& edge : edgeDataPerColor[colorIdx]) {
                    int u = edge.nodeA;
                    int v = edge.nodeB;

                    laplacianMatrix[u][u] = (laplacianMatrix[u][u] + 1) % MODULO_CONST;
                    laplacianMatrix[v][v] = (laplacianMatrix[v][v] + 1) % MODULO_CONST;
                    laplacianMatrix[u][v] = (laplacianMatrix[u][v] - 1 + MODULO_CONST) % MODULO_CONST;
                    laplacianMatrix[v][u] = (laplacianMatrix[v][u] - 1 + MODULO_CONST) % MODULO_CONST;
                }
            }
        }

        // Calcula o sinal de inclusão-exclusão: (-1)^(Total_Cores - Tamanho_Subconjunto)
        long long signMultiplier = ( (numGraphNodes - 1 - subsetSize) % 2 == 0 ) ? 1 : -1;

        // Copia uma submatriz para cálculo do determinante (ex: exclui última linha/coluna).
        // A matriz Laplaciana tem N x N, e precisamos de uma (N-1)x(N-1) submatriz.
        // Se os nós são de 1 a N, removemos a linha N e a coluna N, copiando [1...N-1][1...N-1].
        std::vector<:vector long="">> subMatrix(numGraphNodes - 1, std::vector<long long="">(numGraphNodes - 1));
        for (int i = 0; i < numGraphNodes - 1; ++i) { // Itera de 0 a (N-2)
            for (int j = 0; j < numGraphNodes - 1; ++j) {
                subMatrix[i][j] = laplacianMatrix[i+1][j+1]; // Copia do 1-indexado para 0-indexado
            }
        }

        long long currentDeterminant = computeMatrixDeterminant(subMatrix, numGraphNodes - 1);
        
        finalAnswer = (finalAnswer + (currentDeterminant * signMultiplier) % MODULO_CONST + MODULO_CONST) % MODULO_CONST;
    }

    std::cout << finalAnswer << std::endl;

    return 0;
}
</long></:vector></long></:vector></:vector></int>

Problema 2: Mapeamento Injetivo de Árvore em Grafo Geral

Este problema requer a contagem do número de mapeamentos injetivos de uma árvore \(T\) de \(N\) nós para um grafo geral \(G\), de forma que cada nó da árvore é mapeado para um nó distinto no grafo, e se \((u, v)\) é uma aresta em \(T\), então \((\text{map}(u), \text{map}(v))\) deve ser uma aresta em \(G\).

A natureza "injetiva" e "distinta" torna a contagem direta complexa. Novamente, o Princípio da Inclusão-Exclusão é aplicado, mas desta vez sobre os vértices do grafo geral \(G\). Iteramos sobre todos os subconjuntos \(S\) dos vértices de \(G\). Para cada subconjunto \(S\), calculamos o número de maneiras de mapear a árvore \(T\) para o subgrafo induzido por \(S\) (ignorando a condição de que os nós de \(T\) devem ser mapeados para um número exato de nós em \(G\)). O coeficiente \((-1)^{(\text{total de nós de G} - |S|)}\) é então aplicado.

Para contar o número de mapeamentos de \(T\) para um subgrafo induzido por \(S\), usamos Programação Dinâmica em Árvores. A DP é definida como \(dp[u][i]\), representando o número de maneiras de mapear a subárvore enraizada em \(u\) para o subgrafo induzido por \(S\), tal que o nó \(u\) da árvore é mapeado para o \(i\)-ésimo nó no conjunto \(S\) (denotado como \(selectedNodesIndices[i]\)).

A transição da DP para um nó \(u\) e seu mapeamento \(selectedNodesIndices[i]\) é o produto das somas das possibilidades para seus filhos. Para cada filho \(v\) de \(u\), somamos \(dp[v][j]\) para todos os \(selectedNodesIndices[j]\) que são adjacentes a \(selectedNodesIndices[i]\) no grafo \(G\). A base da DP é para nós folha da árvore, onde \(dp[\text{folha}][i] = 1\) para cada \(selectedNodesIndices[i]\). É importante notar a particularidade da implementação que inclui um '+1' na multiplicação para os filhos, que pode surgir de diferentes interpretações do problema ou da forma de contagem.

O algoritmo geral é:

1. Inicialize a resposta total como 0.
2. Itere sobre todos os \(2^{\text{num\_nós\_grafo}}\) subconjuntos de vértices do grafo \(G\).
3. Para cada subconjunto \(S\):
   1. Liste os vértices de \(S\).
   2. Execute a DP na árvore \(T\) (geralmente uma busca em profundidade):
      1. Para cada nó \(u\) da árvore e para cada índice \(i\) do conjunto \(S\):
         • Inicialize \(dp[u][i] = 1\).
         • Para cada filho \(v\) de \(u\):
           • Calcule \(\text{soma\_opções\_filho} = 0\).
           • Para cada índice \(j\) do conjunto \(S\):
             • Se \(selectedNodesIndices[i]\) e \(selectedNodesIndices[j]\) são adjacentes em \(G\):
               • Adicione \(dp[v][j]\) a \(\text{soma\_opções\_filho}\).
           • Multiplique \(dp[u][i]\) por \((\text{soma\_opções\_filho} + 1)\).
   3. Some \(dp[\text{raiz}][i]\) para todos os \(i\) no conjunto \(S\) para obter a contagem total de mapeamentso para este subconjunto \(S\).
   4. Multiplique pela coeficiente de inclusão-exclusão e adicione/subtraia da resposta total.

#include <iostream>
#include <vector>
#include <numeric> // Para std::fill

const int MAX_GRAPH_VERTICES = 20;

// Matrizes de adjacência para a árvore (treeAdjacency) e o grafo geral (graphAdjacency)
std::vector<std::vector<bool>> treeAdjacency(MAX_GRAPH_VERTICES, std::vector<bool>(MAX_GRAPH_VERTICES, false));
std::vector<std::vector<bool>> graphAdjacency(MAX_GRAPH_VERTICES, std::vector<bool>(MAX_GRAPH_VERTICES, false));

int numTreeNodes;
int numSelectedNodes; // Número atual de nós no subconjunto de G
// Armazena os índices (1-based) dos nós selecionados do grafo G para o subconjunto atual
std::vector<int> selectedNodesIndices(MAX_GRAPH_VERTICES); 
std::vector<int> parentNodeInTree(MAX_GRAPH_VERTICES, 0); // Para controle do DFS na árvore

// Tabela DP: dpTable[node_da_arvore][indice_no_subconjunto_G]
// Contém o número de mapeamentos da subárvore de 'node_da_arvore'
// para o subgrafo induzido pelos nós selecionados, com 'node_da_arvore' mapeado para selectedNodesIndices[indice_no_subconjunto_G]
std::vector<std::vector<unsigned long long>> dpTable(MAX_GRAPH_VERTICES, std::vector<unsigned long long>(MAX_GRAPH_VERTICES, 0));

// Função recursiva para calcular a DP na árvore
void calculateTreeSubtreeMappings(int currentTreeNode) {
    // Inicializa DP para o nó atual. Cada nó da árvore pode ser mapeado para qualquer selectedNodesIndices[i]
    for (int i = 1; i <= numSelectedNodes; ++i) {
        dpTable[currentTreeNode][i] = 1; // Base case: um nó folha pode ser mapeado de 1 forma para cada nó do subconjunto
    }

    // Percorre os vizinhos do currentTreeNode na árvore
    for (int neighbor = 1; neighbor <= numTreeNodes; ++neighbor) {
        if (treeAdjacency[currentTreeNode][neighbor] && parentNodeInTree[currentTreeNode] != neighbor) {
            parentNodeInTree[neighbor] = currentTreeNode; // Define o pai para controle do DFS
            calculateTreeSubtreeMappings(neighbor); // Calcula DP para o filho primeiro

            // Depois que a DP do filho foi calculada, atualiza o DP do nó atual
            for (int mappedToIdx = 1; mappedToIdx <= numSelectedNodes; ++mappedToIdx) { // currentTreeNode mapeia para selectedNodesIndices[mappedToIdx]
                unsigned long long waysForChildSubtree = 0;
                for (int mappedToChildIdx = 1; mappedToChildIdx <= numSelectedNodes; ++mappedToChildIdx) {
                    // Verifica se selectedNodesIndices[mappedToIdx] (para o pai)
                    // e selectedNodesIndices[mappedToChildIdx] (para o filho) são adjacentes no grafo G
                    if (graphAdjacency[selectedNodesIndices[mappedToIdx]][selectedNodesIndices[mappedToChildIdx]]) {
                        waysForChildSubtree += dpTable[neighbor][mappedToChildIdx];
                    }
                }
                // A solução original utiliza (waysForChildSubtree + 1) na multiplicação.
                // Isso implica uma opção adicional, possivelmente não mapear a subárvore do filho para
                // qualquer nó, ou uma interpretação diferente do problema onde o mapeamento do filho é opcional.
                // Dada a restrição "N vértices distintos", essa "+1" é um detalhe específico da implementação original.
                dpTable[currentTreeNode][mappedToIdx] *= (waysForChildSubtree + 1);
            }
        }
    }
}

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

    int numGraphVertices, numGraphEdges;
    std::cin >> numTreeNodes >> numGraphEdges; // N para nós da árvore, M para arestas do grafo G

    for (int i = 0; i < numGraphEdges; ++i) {
        int u, v;
        std::cin >> u >> v;
        graphAdjacency[u][v] = graphAdjacency[v][u] = true;
    }

    for (int i = 0; i < numTreeNodes - 1; ++i) { // Árvore tem N-1 arestas
        int u, v;
        std::cin >> u >> v;
        treeAdjacency[u][v] = treeAdjacency[v][u] = true;
    }

    unsigned long long finalTotalMappings = 0;

    // Iterar sobre todos os subconjuntos possíveis de vértices do grafo G
    // O bitmask representa o subconjunto de nós (0-indexed para bits, 1-indexed para nós)
    for (int subsetMask = 1; subsetMask < (1 << numTreeNodes); ++subsetMask) {
        numSelectedNodes = 0;
        // Preenche o array selectedNodesIndices com os índices (1-based) dos nós no subconjunto atual
        for (int j = 0; j < numTreeNodes; ++j) {
            if ((subsetMask >> j) & 1) { // Se o j-ésimo bit está setado
                selectedNodesIndices[++numSelectedNodes] = j + 1; // Converte bit 0-indexado para nó 1-indexado
            }
        }

        // Calcula o sinal de inclusão-exclusão: (-1)^(Total_Nós_G - Tamanho_Subconjunto)
        int signMultiplier = ( (numTreeNodes - numSelectedNodes) % 2 == 1 ) ? -1 : 1;
        
        // Reseta o array de pais para cada novo cálculo de DP
        std::fill(parentNodeInTree.begin(), parentNodeInTree.end(), 0);

        // Inicia a DP a partir da raiz da árvore (nó 1)
        calculateTreeSubtreeMappings(1);

        unsigned long long currentSubsetMappingsSum = 0;
        for (int i = 1; i <= numSelectedNodes; ++i) {
            currentSubsetMappingsSum += dpTable[1][i]; // Soma para a raiz mapeada para cada nó no subconjunto
        }

        if (signMultiplier == 1) {
            finalTotalMappings += currentSubsetMappingsSum;
        } else {
            finalTotalMappings -= currentSubsetMappingsSum;
        }
    }

    std::cout << finalTotalMappings << std::endl;

    return 0;
}