0x1c - Decir si un nodo es ancestro de otro en un árbol

Un árbol es un grafo con N nodos en el que cada nodo tiene exactamente un padre y cero o más hijos.

En este problema cada nodo en el árbol está identificado por un número único entre 0 y N-1. Aquí hay un ejemplo con N = 9:

En este ejemplo el 0 es el padre de 1, 2 y 3. Del mismo modo los hijos de 6 son 7 y 8.

Decimos que el nodo A es un ancestro del nodo B (ó equivalentemente, B es un descendiente de A) si se cumple una de estas dos opciones:

• B es hijo directo de A (ó equivalentemente, A es el padre directo de B);
• B es hijo de los hijos de A, ó hijo de los hijos de los hijos de A, ó hijo de los hijos de los hijos de los hijos de A y así sucesivamente.

En nuestro ejemplo anterior, el nodo 1 es ancestro de 4 y 5 (porque es su padre directo) y el nodo 3 es ancestro de 6, 7 y 8 (porque es el padre directo de 6 y el padre del padre de 7 y 8).

Por conveniencia, también decimos que un nodo es ancestro de él mismo (por ejemplo, es válido decir que el nodo 2 es ancestro de 2).

El nodo en la parte superior del árbol, también llamado raíz, tiene la propiedad particular de ser ancestro de todos los demás nodos del árbol. En este problema la raíz siempre tiene el número 0.

Escribe un programa que recibe un árbol y varias consultas con valores diferentes de A y B. Para cada consulta, tu programa debe calcular rápidamente si A es un ancestro de B.

Entrada

La entrada contiene varias líneas:

• La primera línea contiene N, el número de nodos en el árbol (1 ≤ N ≤ 100,000).
• Luego vienen N-1 lineas que describen el árbol. Cada línea tiene dos números P y H separados por un espacio. Estos números indican que el nodo P es el padre de H. Está garantizado que 0 ≤ P, H < N (es decir, tanto P como H son nodos válidos), que P ≠ H (un nodo nunca es padre de él mismo) y que H ≠ 0 (la raíz no tiene padre). También está garantizado que el árbol está conectado (es decir, existe un camino para llegar de la raíz a todos los demás nodos).
• La siguiente línea tiene un entero C, el número de consultas (1 ≤ C ≤ 50,000).
• Luego vienen C líneas, cada una con un consulta descrita por dos enteros A y B. Está garantizado que 0 ≤ A, B < N (es decir, tanto A como B son nodos válidos).

Salida

La salida debe tener exactamente C líneas (una por consulta).

Para cada consulta, escribe una línea con la palabra Yes si A es ancestro de B, ó No si A no es ancestro de B.

Entrada de ejemplo

9
0 1
1 4
1 5
0 2
0 3
3 6
6 7
6 8
6
1 4
2 2
3 7
0 8
2 0
5 6

Salida de ejemplo

Yes
Yes
Yes
Yes
No
No

Explicación del ejemplo

La entrada nos da el árbol de la imagen, con N = 9. Luego vienen 6 consultas:

• La primera consulta es A = 1 y B = 4. La respuesta es Yes porque 1 es el padre directo de 4.
• La segunda consulta es A = 2 y B = 2. La respuesta es Yes porque un nodo siempre es ancestro de él mismo.
• La tercera consulta es A = 3 y B = 7. La respuesta es Yes porque 3 es padre del padre de 7.
• La cuarta consulta es A = 0 y B = 8. La respuesta es Yes porque la raíz (0) siempre es ancestro de todos los demás nodos.
• La quinta consulta es A = 2 y B = 0. La respuesta es No porque 2 no es padre de 0 (todo lo contrario, 0 es padre de 2), entonces 2 no es ancestro de 0.
• La sexta consulta es A = 5 y B = 6 y la respuesta también es No.

Envía tu solución