Verificar la validez de un recorrido BFS
Dado un árbol (un grafo sin ciclos) con
n vértices y un recorrido BFS (búsqueda en anchura) que indica la secuencia de los vértices visitados por el algoritmo, se te pide comprobar si dicha secuencia de visitas es posible.El algoritmo siempre comienza en el vértice 1 y recorre los vecinos en un orden no específico. Tu programa debe imprimir
Yes si el recorrido es posible para el árbol dado, o No en caso contrario.Como recordatorio, un árbol siempre tiene
n-1 aristas.Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ 100 000).Las siguientes
n-1 líneas contienen pares de enteros (1 ≤ ≤ n) que representan las aristas.La línea siguiente contiene
n enteros separados por espacios (1 ≤ ≤ n) que describen la secuencia de visitas utilizada por el algoritmo BFS.Salida
El programa debe imprimir
Yes si el escenario dado es válido, y No en caso contrario.Ejemplos
Entrada | Salida |
4
1 2
1 3
2 4
1 2 3 4 | Yes |
4
1 2
1 3
2 4
1 2 4 3 | No |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB