0637-arvore-de-natal

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 637 name: Árvore de Natal origin: wok topics: - programacao-dinamica slug: arvore-de-natal authorSlugEditorial: alessio authorSlugProblem: Unknown description: Otimização Topológica via Programação Dinâmica em Árvores (DP on Trees). O algoritmo instiga DFS iterativas contornando Stack Overflows N=1M para aplicar funções heurísticas bottom-up e minimizar arestas sob tiebreaks de ganho modular. editorial: Utilize Programação Dinâmica em Árvores (DP on Trees). Para cada galho (u, v), a decisão de mantê-lo depende se o ganho acumulado w(u,v) + f(v) é positivo. Se for <= 0, o galho deve ser cortado para maximizar a beleza e minimizar o número de galhos (conforme regra de desempate). Use DFS interativa ou aumente o limite da pilha para lidar com N=10^6. successmsg: Processamento Bottom-Up validado. A travessia instanciou sumários locais exatos em topologias estressantes sem vasamentos de memória ou estouros recursivos, respeitando o Pruning O(V+E). difficultyLevelId: B timeComplexity: O(N) spaceComplexity: O(1) timeLimitSegs: 4 memoryLimitMb: 256 defaultStatement: c_pt_arvore-de-natal.md skills: - bfs-dfs - dp-on-tree - greedy-algorithms - trees statements: - id: a-arvore-de-natal testScenarioLevel: A thematicSkills: - skill: wok points: 1 testScenarios: - id: d-sample name: Exemplo do Enunciado description: Valida o caso base fornecido no enunciado e a formatação básica da saída. helpTip: I/O Format Validation. O buffer de stdout deve despejar o escalar bidimensional (Max_Weight, Cuts) e o array vetorizado estritamente em ordem lexicográfica. level: D testType: TDD skills: - skill: greedy-algorithms points: 1 - skill: trees points: 1 - id: b-linear-deep name: Árvore Linear Profunda description: Uma árvore em forma de linha com 1.000.000 de nós para testar limites de recursão. helpTip: Runtime Stack Overflow Warning. Depth Limits nativos acionarão SegFault O(N). Isole o DFS recursivo transferindo a Stack do PC para alocações locais na Heap estrita (Iterative DFS). level: B testType: TDD skills: - skill: bfs-dfs points: 1 - skill: trees points: 1 - id: b-star-wide name: Árvore Estrela Larga description: Raiz conectada a 999.999 folhas. Testa a eficiência no processamento de muitos filhos. helpTip: Adjacency Matrix Overflow. Concentrações esparsas radiais (Estrela) exigem alocação vetorial em listas de adjacência. Evite varreduras mortas O(N) iterando sobre sub-vetores diretos. level: B testType: TDD skills: - skill: bfs-dfs points: 1 - skill: trees points: 1 - id: c-zero-gain-tiebreak name: Desempate de Ganho Zero description: Casos onde manter ou cortar um galho resulta na mesma beleza. helpTip: Tiebreak Heurístico de Arestas. Se DP(Vertex) == 0, a submissão gulosa impõe 'Pruning' absoluto para minimizar retenção de Vértices e Arestas ineficazes. level: C testType: TDD skills: - skill: greedy-algorithms points: 1 - id: a-performance-load name: Teste de Carga e Performance description: Estrutura complexa com 1.000.000 de nós e pesos variados para testar eficiência máxima. helpTip: Massive Allocation Stress-Test O(N). Time Limits inflados (8s) acomodam overheads de garbage collectors densos, porém as transições DP(u) = Val(u) + sum(max(DP(v), 0)) exigem O(V+E) exato. level: A testType: PERFORMANCE skills: - skill: bfs-dfs points: 1 - skill: dp-on-tree points: 2 - id: c-all-negative name: Todos Pesos Negativos description: Cenário onde todos os galhos são feios (pesos negativos). helpTip: Grafo Degenerado Negativo. A matriz ótima despencará todos os fluxos para perdas. O base-case garante extração e isolamento estrito O(1) do nó Root. level: C testType: TDD skills: - skill: greedy-algorithms points: 1 - skill: dp-on-tree points: 1 solutions: - id: a-optimal name: Solução Ótima description: Abordagem de Programação Dinâmica em Árvores processada de forma iterativa para garantir eficiência O(N) e segurança contra estouro de pilha. level: A implementations: - filenames: - optimal.cpp language: cpp paradigm: Imperative - filenames: - Optimal.java language: java paradigm: Imperative main: Optimal - filenames: - Natal.java language: java paradigm: Imperative main: Natal - filenames: - optimal.py language: py paradigm: Imperative - filenames: - natal.py language: py paradigm: Imperative - id: b-suboptimal name: Solução Sub-ótima (Recursiva) description: Abordagem recursiva padrão em Python que falha em entradas grandes devido ao limite de profundidade de recursão. level: B implementations: - filenames: - suboptimal.py language: py paradigm: Imperative