CF1037D Valid BFS?

[BFS](https://en.wikipedia.org/wiki/Breadth-first_search) 算法定义如下： 1. 给定一个顶点编号为 $1$ 到 $n$ 的无向图。初始化队列 $q$，仅包含顶点 $1$，并将顶点 $1$ 标记为已访问。 2. 从队列 $q$ 的队首取出一个顶点 $v$。 3. 输出顶点 $v$ 的编号。 4. 按任意顺序遍历所有满足条件的顶点 $u$，其中 $u$ 是 $v$ 的邻居且尚未被标记为已访问。将顶点 $u$ 标记为已访问，并插入到队列 $q$ 的队尾。 5. 如果队列不为空，则返回第 2 步。 6. 否则算法结束。 由于每个顶点的邻居选择顺序可以不同，因此 BFS 可能输出多种不同的遍历序列。 本题要求你判断，给定的一个序列是否可能是从顶点 $1$ 开始对给定树进行 BFS 遍历得到的某种合法顺序。这里的“树”指的是一个无向图，任意两点之间恰好有一条简单路径。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示树的节点数。 接下来的 $n-1$ 行描述树的边。每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示树的一条边的两个端点。保证给定的图是一棵树。 最后一行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示需要检查的序列。

如果该序列是某种合法的 BFS 遍历顺序，输出 "Yes"；否则输出 "No"。输出时不区分大小写。

两个样例测试用例中使用的是同一棵树。 对于这棵树，有两种合法的 BFS 遍历顺序： - $1, 2, 3, 4$， - $1, 3, 2, 4$。 序列 $1, 2, 4, 3$ 不对应于任何合法的 BFS 遍历顺序。 由 ChatGPT 4.1 翻译