Überprüfung der Gültigkeit einer BFS-Traversierung
Angenommen, wir haben einen Baum (ein Graph ohne Zyklen) mit
n Knoten und eine BFS-Traversierung, die die Reihenfolge der vom Algorithmus besuchten Knoten angibt. Unsere Aufgabe ist zu prüfen, ob diese Besuchsreihenfolge überhaupt möglich ist.Der Algorithmus startet immer beim Knoten 1 und durchläuft die benachbarten Knoten in beliebiger Reihenfolge. Ihr Programm soll
Yes ausgeben, wenn die angegebene Traversierung für den gegebenen Baum möglich ist, und andernfalls No.Zur Erinnerung: Ein Baum hat immer
n-1 Kanten.Eingabe
Die erste Zeile der Eingabe enthält eine ganze Zahl
n (1 ≤ n ≤ 100 000).Die folgenden
n-1 Zeilen enthalten jeweils zwei ganze Zahlen (1 ≤ ≤ n), die die Kanten des Baums darstellen.In der darauffolgenden Zeile stehen
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ n), die die Besuchsreihenfolge des BFS-Algorithmus angeben.Ausgabe
Das Programm soll
Yes ausgeben, wenn das beschriebene Szenario gültig ist, andernfalls No.Beispiele
Input | Output |
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