BFS トラバーサルの正当性を確認する
サイクルを含まないグラフ（木）として頂点数が
n の木が与えられており、BFS アルゴリズムによる訪問順序が示されています。このとき、その訪問順序が実際にあり得るかどうかを判定する問題です。アルゴリズムは常に頂点 1 から開始し、近接する頂点を特定の順番ではなく任意の順番で探索します。与えられた木に対してその訪問順序が可能であれば
Yes、そうでなければ No を出力してください。なお、木は必ず
n-1 本の辺を持つことを思い出してください。入力
最初の行には整数
n (1 ≤ n ≤ 100000) が与えられます。続く
n-1 行には、それぞれ (1 ≤ ≤ n) という形式で辺が与えられます。その後の行には、BFS アルゴリズムの訪問順序を表す
n 個の整数 (1 ≤ ≤ n) が空白区切りで与えられます。出力
与えられたシナリオが成立する場合は
Yes、そうでない場合は No を出力してください。例
入力 | 出力 |
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