uCoder | 1289 | Nível: 5 | Tempo Limite: 10
Fundindo árvores
Adaptado por Erich Rodrigues
Competição: SBC - ACM/ICPC - Maratona de Programação de 2016
Em Computação árvores são objetos estranhos: a raiz está no topo e as folhas estão embaixo! Uma árvore é uma estrutura de dados composta de N vértices conectados por N 1 arestas de forma que é possível chegar de um vértice a qualquer outro vértice seguindo as arestas. Em uma árvore enraizada, cada aresta conecta um vértice pai a um vértice filho. Um único vértice não tem pai, e é chamado de raiz. Assim, partir da raiz é possivel chegar a qualquer outro vértice da árvore seguindo as arestas na direção de pai para filho.
Em uma árvore ternária cada vértice pode ter até três vértices filhos, chamados esquerdo, central e direito. Uma árvore ternária canhota é uma árvore ternária enraizada em que nenhum vértice tem filho direito. Uma árvore ternária destra é uma árvore ternária enraizada em que nenhum vértice tem filho esquerdo. A raiz de uma árvore ternária é sempre um vértice central. A figura abaixo mostra exemplos de uma árvore canhota e de uma árvore destra.
A superposição S de uma árvore canhota C com uma árvore destra D é uma árvore ternária enraizada em que a raiz é ou a raiz de C ou a raiz de D ou ambas as raízes, de C e de D, superpostas, e que contém a estrutura de ambas as árvores superpostas. A figura abaixo mostra algumas árvores formadas pela superposição da árvore canhota e da árvore destra da figura acima.
Note que na Figura (a) a raiz é o vértice x (da árvore destra) e os pares de vértices (a, y) e (c, u) são superpostos. Na Figura (b) a raiz é o vértice a (da árvore canhota) e os pares de vértices (d, x), (e, y) e (f, u) são superpostos. Na Figura (c) a raiz também é o vértice a (da árvore canhota) e o par de vértices (f, x) é superposto.
Dadas uma árvore canhota e uma árvore destra, sua tarefa é determinar o número mínimo de vértices necessários para construir uma árvore ternária que é uma superposição das árvores dadas.
Entrada
A primeira linha de um caso de teste contém um inteiro N indicando o número de vértices da árvore canhota (1 ≤ N ≤ 104 ). Vértices nesta árvore são identificados por números de 1 a N , e a raiz é o vértice de número 1. Cada uma das N linhas seguintes contém três inteiros I, L e K, indicando respectivamente o identificador de um vértice I, o identificador do filho esquerdo L de I e o identificador do filho central K de I (0 ≤ I, L, K ≤ N ). A linha seguinte contém um inteiro M indicando o número de vértices da árvore destra (1 ≤ M ≤ 104 ). Vértices nesta árvore são identificados por números de 1 a M , e a raiz é o vértice de número 1. Cada uma das M linhas seguintes contém três inteiros P , Q e R, indicando respectivamente o identificador de um vértice P , o identificador do filho central Q de P e o identificador do filho direito R de P (0 ≤ P, Q, R ≤ N ). O valor zero indica um vértice não existente (usado quando um vértice não tem um ou ambos os seus filhos).
Saída
Imprima o número mínimo de vértices de uma árvore que é a superposição das duas árvores dadas na entrada.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
3 |
3 |
|
5 |
6 |
|
7 |
11 |