← 返回题目列表

Codeforces · 1037/D

D. 有效的 BFS?

中文机器翻译题面 查看原题

BFS算法定义如下。

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 遍历,则打印“是”(为了清楚起见,加引号),否则打印“否”(为了清楚起见,加引号)。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

4
1 2
1 3
2 4
1 2 3 4

输出 #1

Yes

输入 #2

4
1 2
1 3
2 4
1 2 4 3

输出 #2

No

注意

两个示例测试都具有相同的树。

在这棵树中,有两个有效的 BFS 排序:

- $$$1, 2, 3, 4$$$,
- $$$1, 3, 2, 4$$$.

排序 $$$1, 2, 4, 3$$$ 不对应于任何有效的 BFS 订单。