uCoder - Fundindo árvores
Fundindo árvores
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.
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).