1928-jogo-da-memoria

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 1928 name: "Jogo da Memória" slug: "jogo-da-memoria" timelimit: 2.0 memlimit: 200 difficultyLevelId: D author: "Maratona de Programacao da SBC" origin: "Beecrowd" description: 'Encontre a soma das distâncias entre pares de cartas idênticas em uma estrutura de Árvore usando o algoritmo de Menor Ancestral Comum (LCA).' editorial: | O problema descreve $N$ cartas e $N-1$ ligações (arestas) onde existe um único caminho entre qualquer par de cartas. Esta é a exata definição de uma Árvore! Para encontrar os pontos de um par, precisamos calcular a distância entre os dois nós na árvore. Como $N \le 50000$ e precisaremos consultar a distância de $N/2$ pares, uma busca (BFS/DFS) para cada par custaria O(N^2) e daria TLE. A solução ideal exige a técnica LCA (Lowest Common Ancestor - Menor Ancestral Comum) com Binary Lifting (Subida Binária). A distância entre u e v é dada por: Dist(u, v) = depth[u] + depth[v] - 2 * depth[LCA(u, v)]. Pré-computamos os saltos binários em O(N log N) e depois respondemos cada par em O(log N). A complexidade total é estritamente O(N log N). successmsg: 'Sensacional! Dominar o LCA com Binary Lifting eleva seu patamar em Grafos/Árvores para o nível de competidor profissional.' timeComplexity: O(N \log N) skills: - graphs - lca statements: - id: a-memoria testScenarioLevel: A thematicSkills: - skill: graphs points: 2 testScenarios: - id: a-performance name: Árvore Monstro description: "Árvore linha reta com 50000 nós." helpTip: "Você usou LCA com Subida Binária? Uma busca simples por par resultará em tempo quadrático e TLE." level: A testType: PERFORMANCE skills: - skill: lca points: 1 - id: b-fuzzing name: Árvores Aleatórias description: "Grafos gerados como árvores aleatórias e cartas embaralhadas." helpTip: "Cuidado com o limite de profundidade e o caso base de folhas no mesmo nível." level: B testType: TDD skills: - skill: lca points: 1 - id: c-edge name: Estrela Completa description: "Um nó central ligado a todos os outros." helpTip: "A profundidade de quase todos os nós é 1. O LCA será quase sempre a raiz." level: C testType: TDD skills: - skill: graphs points: 1 - id: d-sample name: Exemplo do Enunciado description: "Caso básico do problema." helpTip: "Passe o exemplo." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: LCA com Binary Lifting description: Pré-computa subidas 2^i e acha o ancestral comum em O(log N). level: A implementations: - language: cpp paradigm: Imperative main: memoria.cpp filenames: - memoria.cpp - language: py paradigm: Imperative main: memoria.py filenames: - memoria.py - language: java paradigm: OO main: Memoria filenames: - Memoria.java authorSlugProblem: Unknown defaultStatement: a-memoria