Проверка корректности обхода BFS
Дано дерево (граф без циклов) с
n вершинами и заданный порядок обхода BFS, указывающий последовательность вершин, которые алгоритм посетил. Необходимо проверить, возможна ли такая последовательность посещений.Алгоритм всегда начинает обход с вершины 1 и обходит соседние вершины в произвольном порядке. Ваша программа должна вывести
Yes, если такой порядок обхода действительно возможен для данного дерева, и No — если нет.Напомним, что в дереве всегда ровно
n-1 ребро.Входные данные
В первой строке входного файла содержится одно целое число
n (1 ≤ n ≤ 100 000).В следующих
n-1 строках даны пары целых чисел (1 ≤ ≤ n), задающие ребра этого дерева.В следующей строке приведены
n целых чисел (1 ≤ ≤ n), разделенных пробелами, которые обозначают порядок обхода алгоритмом BFS.Выходные данные
Программа должна вывести
Yes, если указанный сценарий является корректным, и No в противном случае.Примеры
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