Vérification de la validité d'un parcours BFS
Étant donné un arbre (un graphe sans cycles) composé de
n sommets et un parcours BFS (Breadth-First Search) qui fournit la séquence de sommets visités par l’algorithme, il vous est demandé de déterminer si cette séquence de visites est possible.L’algorithme commence toujours par le sommet 1 et parcourt ses voisins dans un ordre quelconque. Votre programme devra afficher
Yes si ce parcours est réalisable pour l’arbre donné, ou No dans le cas contraire.Pour rappel, un arbre possède toujours
n-1 arêtes.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000).Les
n-1 lignes suivantes contiennent des paires d’entiers (1 ≤ ≤ n) représentant les arêtes de l’arbre.La ligne suivante contient
n entiers séparés par des espaces, (1 ≤ ≤ n), qui indiquent l’ordre dans lequel le parcours BFS a visité les sommets.Sortie
Le programme doit afficher
Yes si la séquence de visites donnée est possible, et No sinon.Exemples
Entrée | Sortie |
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